X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FScalarEvolutionExpander.h;h=816d49764d159c5b3841b425a0728844e05ba04d;hb=76f600b205606a055ec35e7d3fd1a99602329d67;hp=3e05ab0c09706fe82eb15e0679b0ee62d03e9219;hpb=d29b6aa608d69f19b57ebd2ae630b040b1c4951d;p=oota-llvm.git diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h index 3e05ab0c097..816d49764d1 100644 --- a/include/llvm/Analysis/ScalarEvolutionExpander.h +++ b/include/llvm/Analysis/ScalarEvolutionExpander.h @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -14,163 +14,106 @@ #ifndef LLVM_ANALYSIS_SCALAREVOLUTION_EXPANDER_H #define LLVM_ANALYSIS_SCALAREVOLUTION_EXPANDER_H -#include "llvm/BasicBlock.h" -#include "llvm/Constants.h" -#include "llvm/Instructions.h" -#include "llvm/Type.h" -#include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" -#include "llvm/Support/CFG.h" +#include "llvm/Support/IRBuilder.h" +#include "llvm/Support/TargetFolder.h" namespace llvm { /// SCEVExpander - This class uses information about analyze scalars to /// rewrite expressions in canonical form. /// /// Clients should create an instance of this class when rewriting is needed, - /// and destroying it when finished to allow the release of the associated + /// and destroy it when finished to allow the release of the associated /// memory. struct SCEVExpander : public SCEVVisitor { ScalarEvolution &SE; - LoopInfo &LI; - std::map InsertedExpressions; - std::set InsertedInstructions; + std::map, AssertingVH > + InsertedExpressions; + std::set InsertedValues; - Instruction *InsertPt; + typedef IRBuilder BuilderType; + BuilderType Builder; friend struct SCEVVisitor; public: - SCEVExpander(ScalarEvolution &se, LoopInfo &li) : SE(se), LI(li) {} + explicit SCEVExpander(ScalarEvolution &se) + : SE(se), Builder(TargetFolder(se.TD, se.getContext())) {} /// clear - Erase the contents of the InsertedExpressions map so that users /// trying to expand the same expression into multiple BasicBlocks or /// different places within the same BasicBlock can do so. void clear() { InsertedExpressions.clear(); } - /// isInsertedInstruction - Return true if the specified instruction was - /// inserted by the code rewriter. If so, the client should not modify the - /// instruction. - bool isInsertedInstruction(Instruction *I) const { - return InsertedInstructions.count(I); - } - /// getOrInsertCanonicalInductionVariable - This method returns the /// canonical induction variable of the specified type for the specified /// loop (inserting one if there is none). A canonical induction variable /// starts at zero and steps by one on each iteration. - Value *getOrInsertCanonicalInductionVariable(const Loop *L, const Type *Ty){ - assert((Ty->isInteger() || Ty->isFloatingPoint()) && - "Can only insert integer or floating point induction variables!"); - SCEVHandle H = SCEVAddRecExpr::get(SCEVUnknown::getIntegerSCEV(0, Ty), - SCEVUnknown::getIntegerSCEV(1, Ty), L); - return expand(H); - } - - /// addInsertedValue - Remember the specified instruction as being the - /// canonical form for the specified SCEV. - void addInsertedValue(Instruction *I, SCEV *S) { - InsertedExpressions[S] = (Value*)I; - InsertedInstructions.insert(I); - } + Value *getOrInsertCanonicalInductionVariable(const Loop *L, const Type *Ty); /// expandCodeFor - Insert code to directly compute the specified SCEV /// expression into the program. The inserted code is inserted into the /// specified block. - /// - /// If a particular value sign is required, a type may be specified for the - /// result. - Value *expandCodeFor(SCEVHandle SH, Instruction *IP, const Type *Ty = 0) { - // Expand the code for this SCEV. - this->InsertPt = IP; - return expandInTy(SH, Ty); + Value *expandCodeFor(const SCEV* SH, const Type *Ty, Instruction *IP) { + Builder.SetInsertPoint(IP->getParent(), IP); + return expandCodeFor(SH, Ty); } - protected: - Value *expand(SCEV *S) { - // Check to see if we already expanded this. - std::map::iterator I = InsertedExpressions.find(S); - if (I != InsertedExpressions.end()) - return I->second; + private: + LLVMContext *getContext() const { return SE.getContext(); } + + /// InsertBinop - Insert the specified binary operator, doing a small amount + /// of work to avoid inserting an obviously redundant operation. + Value *InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, Value *RHS); - Value *V = visit(S); - InsertedExpressions[S] = V; - return V; - } + /// InsertNoopCastOfTo - Insert a cast of V to the specified type, + /// which must be possible with a noop cast, doing what we can to + /// share the casts. + Value *InsertNoopCastOfTo(Value *V, const Type *Ty); - Value *expandInTy(SCEV *S, const Type *Ty) { - Value *V = expand(S); - if (Ty && V->getType() != Ty) { - // FIXME: keep track of the cast instruction. - if (Constant *C = dyn_cast(V)) - return ConstantExpr::getCast(C, Ty); - else if (Instruction *I = dyn_cast(V)) { - // Check to see if there is already a cast. If there is, use it. - for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); - UI != E; ++UI) { - if ((*UI)->getType() == Ty) - if (CastInst *CI = dyn_cast(cast(*UI))) { - BasicBlock::iterator It = I; ++It; - if (isa(I)) - It = cast(I)->getNormalDest()->begin(); - while (isa(It)) ++It; - if (It != BasicBlock::iterator(CI)) { - // Splice the cast immediately after the operand in question. - BasicBlock::InstListType &InstList = - It->getParent()->getInstList(); - InstList.splice(It, CI->getParent()->getInstList(), CI); - } - return CI; - } - } - BasicBlock::iterator IP = I; ++IP; - if (InvokeInst *II = dyn_cast(I)) - IP = II->getNormalDest()->begin(); - while (isa(IP)) ++IP; - return new CastInst(V, Ty, V->getName(), IP); - } else { - // FIXME: check to see if there is already a cast! - return new CastInst(V, Ty, V->getName(), InsertPt); - } - } - return V; + /// expandAddToGEP - Expand a SCEVAddExpr with a pointer type into a GEP + /// instead of using ptrtoint+arithmetic+inttoptr. + Value *expandAddToGEP(const SCEV* const *op_begin, + const SCEV* const *op_end, + const PointerType *PTy, const Type *Ty, Value *V); + + Value *expand(const SCEV *S); + + /// expandCodeFor - Insert code to directly compute the specified SCEV + /// expression into the program. The inserted code is inserted into the + /// SCEVExpander's current insertion point. If a type is specified, the + /// result will be expanded to have that type, with a cast if necessary. + Value *expandCodeFor(const SCEV* SH, const Type *Ty = 0); + + /// isInsertedInstruction - Return true if the specified instruction was + /// inserted by the code rewriter. If so, the client should not modify the + /// instruction. + bool isInsertedInstruction(Instruction *I) const { + return InsertedValues.count(I); } - Value *visitConstant(SCEVConstant *S) { + Value *visitConstant(const SCEVConstant *S) { return S->getValue(); } - Value *visitTruncateExpr(SCEVTruncateExpr *S) { - Value *V = expand(S->getOperand()); - return new CastInst(V, S->getType(), "tmp.", InsertPt); - } + Value *visitTruncateExpr(const SCEVTruncateExpr *S); - Value *visitZeroExtendExpr(SCEVZeroExtendExpr *S) { - Value *V = expandInTy(S->getOperand(),S->getType()->getUnsignedVersion()); - return new CastInst(V, S->getType(), "tmp.", InsertPt); - } + Value *visitZeroExtendExpr(const SCEVZeroExtendExpr *S); - Value *visitAddExpr(SCEVAddExpr *S) { - const Type *Ty = S->getType(); - Value *V = expandInTy(S->getOperand(S->getNumOperands()-1), Ty); + Value *visitSignExtendExpr(const SCEVSignExtendExpr *S); - // Emit a bunch of add instructions - for (int i = S->getNumOperands()-2; i >= 0; --i) - V = BinaryOperator::createAdd(V, expandInTy(S->getOperand(i), Ty), - "tmp.", InsertPt); - return V; - } + Value *visitAddExpr(const SCEVAddExpr *S); - Value *visitMulExpr(SCEVMulExpr *S); + Value *visitMulExpr(const SCEVMulExpr *S); - Value *visitUDivExpr(SCEVUDivExpr *S) { - const Type *Ty = S->getType(); - Value *LHS = expandInTy(S->getLHS(), Ty); - Value *RHS = expandInTy(S->getRHS(), Ty); - return BinaryOperator::createDiv(LHS, RHS, "tmp.", InsertPt); - } + Value *visitUDivExpr(const SCEVUDivExpr *S); + + Value *visitAddRecExpr(const SCEVAddRecExpr *S); + + Value *visitSMaxExpr(const SCEVSMaxExpr *S); - Value *visitAddRecExpr(SCEVAddRecExpr *S); + Value *visitUMaxExpr(const SCEVUMaxExpr *S); - Value *visitUnknown(SCEVUnknown *S) { + Value *visitUnknown(const SCEVUnknown *S) { return S->getValue(); } };