LLVM API Documentation
00001 //===---- llvm/Analysis/ScalarEvolutionExpander.h - SCEV Exprs --*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file defines the classes used to generate code from scalar expressions. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #ifndef LLVM_ANALYSIS_SCALAREVOLUTION_EXPANDER_H 00015 #define LLVM_ANALYSIS_SCALAREVOLUTION_EXPANDER_H 00016 00017 #include "llvm/BasicBlock.h" 00018 #include "llvm/Constants.h" 00019 #include "llvm/Instructions.h" 00020 #include "llvm/Type.h" 00021 #include "llvm/Analysis/ScalarEvolution.h" 00022 #include "llvm/Analysis/ScalarEvolutionExpressions.h" 00023 #include "llvm/Support/CFG.h" 00024 00025 namespace llvm { 00026 /// SCEVExpander - This class uses information about analyze scalars to 00027 /// rewrite expressions in canonical form. 00028 /// 00029 /// Clients should create an instance of this class when rewriting is needed, 00030 /// and destroying it when finished to allow the release of the associated 00031 /// memory. 00032 struct SCEVExpander : public SCEVVisitor<SCEVExpander, Value*> { 00033 ScalarEvolution &SE; 00034 LoopInfo &LI; 00035 std::map<SCEVHandle, Value*> InsertedExpressions; 00036 std::set<Instruction*> InsertedInstructions; 00037 00038 Instruction *InsertPt; 00039 00040 friend struct SCEVVisitor<SCEVExpander, Value*>; 00041 public: 00042 SCEVExpander(ScalarEvolution &se, LoopInfo &li) : SE(se), LI(li) {} 00043 00044 LoopInfo &getLoopInfo() const { return LI; } 00045 00046 /// clear - Erase the contents of the InsertedExpressions map so that users 00047 /// trying to expand the same expression into multiple BasicBlocks or 00048 /// different places within the same BasicBlock can do so. 00049 void clear() { InsertedExpressions.clear(); } 00050 00051 /// isInsertedInstruction - Return true if the specified instruction was 00052 /// inserted by the code rewriter. If so, the client should not modify the 00053 /// instruction. 00054 bool isInsertedInstruction(Instruction *I) const { 00055 return InsertedInstructions.count(I); 00056 } 00057 00058 /// getOrInsertCanonicalInductionVariable - This method returns the 00059 /// canonical induction variable of the specified type for the specified 00060 /// loop (inserting one if there is none). A canonical induction variable 00061 /// starts at zero and steps by one on each iteration. 00062 Value *getOrInsertCanonicalInductionVariable(const Loop *L, const Type *Ty){ 00063 assert((Ty->isInteger() || Ty->isFloatingPoint()) && 00064 "Can only insert integer or floating point induction variables!"); 00065 SCEVHandle H = SCEVAddRecExpr::get(SCEVUnknown::getIntegerSCEV(0, Ty), 00066 SCEVUnknown::getIntegerSCEV(1, Ty), L); 00067 return expand(H); 00068 } 00069 00070 /// addInsertedValue - Remember the specified instruction as being the 00071 /// canonical form for the specified SCEV. 00072 void addInsertedValue(Instruction *I, SCEV *S) { 00073 InsertedExpressions[S] = (Value*)I; 00074 InsertedInstructions.insert(I); 00075 } 00076 00077 /// expandCodeFor - Insert code to directly compute the specified SCEV 00078 /// expression into the program. The inserted code is inserted into the 00079 /// specified block. 00080 /// 00081 /// If a particular value sign is required, a type may be specified for the 00082 /// result. 00083 Value *expandCodeFor(SCEVHandle SH, Instruction *IP, const Type *Ty = 0) { 00084 // Expand the code for this SCEV. 00085 this->InsertPt = IP; 00086 return expandInTy(SH, Ty); 00087 } 00088 00089 /// InsertCastOfTo - Insert a cast of V to the specified type, doing what 00090 /// we can to share the casts. 00091 static Value *InsertCastOfTo(Value *V, const Type *Ty); 00092 00093 protected: 00094 Value *expand(SCEV *S) { 00095 // Check to see if we already expanded this. 00096 std::map<SCEVHandle, Value*>::iterator I = InsertedExpressions.find(S); 00097 if (I != InsertedExpressions.end()) 00098 return I->second; 00099 00100 Value *V = visit(S); 00101 InsertedExpressions[S] = V; 00102 return V; 00103 } 00104 00105 Value *expandInTy(SCEV *S, const Type *Ty) { 00106 Value *V = expand(S); 00107 if (Ty && V->getType() != Ty) 00108 return InsertCastOfTo(V, Ty); 00109 return V; 00110 } 00111 00112 Value *visitConstant(SCEVConstant *S) { 00113 return S->getValue(); 00114 } 00115 00116 Value *visitTruncateExpr(SCEVTruncateExpr *S) { 00117 Value *V = expand(S->getOperand()); 00118 return new CastInst(V, S->getType(), "tmp.", InsertPt); 00119 } 00120 00121 Value *visitZeroExtendExpr(SCEVZeroExtendExpr *S) { 00122 Value *V = expandInTy(S->getOperand(),S->getType()->getUnsignedVersion()); 00123 return new CastInst(V, S->getType(), "tmp.", InsertPt); 00124 } 00125 00126 Value *visitAddExpr(SCEVAddExpr *S) { 00127 const Type *Ty = S->getType(); 00128 Value *V = expandInTy(S->getOperand(S->getNumOperands()-1), Ty); 00129 00130 // Emit a bunch of add instructions 00131 for (int i = S->getNumOperands()-2; i >= 0; --i) 00132 V = BinaryOperator::createAdd(V, expandInTy(S->getOperand(i), Ty), 00133 "tmp.", InsertPt); 00134 return V; 00135 } 00136 00137 Value *visitMulExpr(SCEVMulExpr *S); 00138 00139 Value *visitSDivExpr(SCEVSDivExpr *S) { 00140 const Type *Ty = S->getType(); 00141 Value *LHS = expandInTy(S->getLHS(), Ty); 00142 Value *RHS = expandInTy(S->getRHS(), Ty); 00143 return BinaryOperator::createDiv(LHS, RHS, "tmp.", InsertPt); 00144 } 00145 00146 Value *visitAddRecExpr(SCEVAddRecExpr *S); 00147 00148 Value *visitUnknown(SCEVUnknown *S) { 00149 return S->getValue(); 00150 } 00151 }; 00152 } 00153 00154 #endif 00155