1 //===---- llvm/Analysis/ScalarEvolutionExpander.h - SCEV Exprs --*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines the classes used to generate code from scalar expressions.
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_ANALYSIS_SCALAREVOLUTION_EXPANDER_H
15 #define LLVM_ANALYSIS_SCALAREVOLUTION_EXPANDER_H
17 #include "llvm/BasicBlock.h"
18 #include "llvm/Constants.h"
19 #include "llvm/Instructions.h"
20 #include "llvm/Type.h"
21 #include "llvm/Analysis/ScalarEvolution.h"
22 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
23 #include "llvm/Support/CFG.h"
26 /// SCEVExpander - This class uses information about analyze scalars to
27 /// rewrite expressions in canonical form.
29 /// Clients should create an instance of this class when rewriting is needed,
30 /// and destroying it when finished to allow the release of the associated
32 struct SCEVExpander : public SCEVVisitor<SCEVExpander, Value*> {
35 std::map<SCEVHandle, Value*> InsertedExpressions;
36 std::set<Instruction*> InsertedInstructions;
38 Instruction *InsertPt;
40 friend struct SCEVVisitor<SCEVExpander, Value*>;
42 SCEVExpander(ScalarEvolution &se, LoopInfo &li) : SE(se), LI(li) {}
44 /// clear - Erase the contents of the InsertedExpressions map so that users
45 /// trying to expand the same expression into multiple BasicBlocks or
46 /// different places within the same BasicBlock can do so.
47 void clear() { InsertedExpressions.clear(); }
49 /// isInsertedInstruction - Return true if the specified instruction was
50 /// inserted by the code rewriter. If so, the client should not modify the
52 bool isInsertedInstruction(Instruction *I) const {
53 return InsertedInstructions.count(I);
56 /// getOrInsertCanonicalInductionVariable - This method returns the
57 /// canonical induction variable of the specified type for the specified
58 /// loop (inserting one if there is none). A canonical induction variable
59 /// starts at zero and steps by one on each iteration.
60 Value *getOrInsertCanonicalInductionVariable(const Loop *L, const Type *Ty){
61 assert((Ty->isInteger() || Ty->isFloatingPoint()) &&
62 "Can only insert integer or floating point induction variables!");
63 SCEVHandle H = SCEVAddRecExpr::get(SCEVUnknown::getIntegerSCEV(0, Ty),
64 SCEVUnknown::getIntegerSCEV(1, Ty), L);
68 /// addInsertedValue - Remember the specified instruction as being the
69 /// canonical form for the specified SCEV.
70 void addInsertedValue(Instruction *I, SCEV *S) {
71 InsertedExpressions[S] = (Value*)I;
72 InsertedInstructions.insert(I);
75 /// expandCodeFor - Insert code to directly compute the specified SCEV
76 /// expression into the program. The inserted code is inserted into the
79 /// If a particular value sign is required, a type may be specified for the
81 Value *expandCodeFor(SCEVHandle SH, Instruction *IP, const Type *Ty = 0) {
82 // Expand the code for this SCEV.
84 return expandInTy(SH, Ty);
88 Value *expand(SCEV *S) {
89 // Check to see if we already expanded this.
90 std::map<SCEVHandle, Value*>::iterator I = InsertedExpressions.find(S);
91 if (I != InsertedExpressions.end())
95 InsertedExpressions[S] = V;
99 Value *expandInTy(SCEV *S, const Type *Ty) {
100 Value *V = expand(S);
101 if (Ty && V->getType() != Ty) {
102 // FIXME: keep track of the cast instruction.
103 if (Constant *C = dyn_cast<Constant>(V))
104 return ConstantExpr::getCast(C, Ty);
105 else if (Instruction *I = dyn_cast<Instruction>(V)) {
106 // Check to see if there is already a cast. If there is, use it.
107 for (Value::use_iterator UI = I->use_begin(), E = I->use_end();
109 if ((*UI)->getType() == Ty)
110 if (CastInst *CI = dyn_cast<CastInst>(cast<Instruction>(*UI))) {
111 BasicBlock::iterator It = I; ++It;
112 if (isa<InvokeInst>(I))
113 It = cast<InvokeInst>(I)->getNormalDest()->begin();
114 while (isa<PHINode>(It)) ++It;
115 if (It != BasicBlock::iterator(CI)) {
116 // Splice the cast immediately after the operand in question.
117 BasicBlock::InstListType &InstList =
118 It->getParent()->getInstList();
119 InstList.splice(It, CI->getParent()->getInstList(), CI);
124 BasicBlock::iterator IP = I; ++IP;
125 if (InvokeInst *II = dyn_cast<InvokeInst>(I))
126 IP = II->getNormalDest()->begin();
127 while (isa<PHINode>(IP)) ++IP;
128 return new CastInst(V, Ty, V->getName(), IP);
130 // FIXME: check to see if there is already a cast!
131 return new CastInst(V, Ty, V->getName(), InsertPt);
137 Value *visitConstant(SCEVConstant *S) {
138 return S->getValue();
141 Value *visitTruncateExpr(SCEVTruncateExpr *S) {
142 Value *V = expand(S->getOperand());
143 return new CastInst(V, S->getType(), "tmp.", InsertPt);
146 Value *visitZeroExtendExpr(SCEVZeroExtendExpr *S) {
147 Value *V = expandInTy(S->getOperand(),S->getType()->getUnsignedVersion());
148 return new CastInst(V, S->getType(), "tmp.", InsertPt);
151 Value *visitAddExpr(SCEVAddExpr *S) {
152 const Type *Ty = S->getType();
153 Value *V = expandInTy(S->getOperand(S->getNumOperands()-1), Ty);
155 // Emit a bunch of add instructions
156 for (int i = S->getNumOperands()-2; i >= 0; --i)
157 V = BinaryOperator::createAdd(V, expandInTy(S->getOperand(i), Ty),
162 Value *visitMulExpr(SCEVMulExpr *S);
164 Value *visitUDivExpr(SCEVUDivExpr *S) {
165 const Type *Ty = S->getType();
166 Value *LHS = expandInTy(S->getLHS(), Ty);
167 Value *RHS = expandInTy(S->getRHS(), Ty);
168 return BinaryOperator::createDiv(LHS, RHS, "tmp.", InsertPt);
171 Value *visitAddRecExpr(SCEVAddRecExpr *S);
173 Value *visitUnknown(SCEVUnknown *S) {
174 return S->getValue();