X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FAnalysis%2FScalarEvolutionExpander.h;h=730c97fff4d7e4295b47979b0e4fafd31733beb3;hb=40a5a1b39ee1cd40ff9d04740386b667fb27b340;hp=8a994b322ab4cb23a3c5cfa6db4c9a5753ffb393;hpb=b2f3e703bcde5833ff5910922f7a5313cc6b1c64;p=oota-llvm.git diff --git a/include/llvm/Analysis/ScalarEvolutionExpander.h b/include/llvm/Analysis/ScalarEvolutionExpander.h index 8a994b322ab..730c97fff4d 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,13 +14,10 @@ #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" namespace llvm { /// SCEVExpander - This class uses information about analyze scalars to @@ -31,17 +28,15 @@ namespace llvm { /// memory. struct SCEVExpander : public SCEVVisitor { ScalarEvolution &SE; - LoopInfo &LI; - std::map InsertedExpressions; - std::set InsertedInstructions; + std::map > InsertedExpressions; + std::set InsertedValues; - Instruction *InsertPt; + BasicBlock::iterator InsertPt; friend struct SCEVVisitor; public: - SCEVExpander(ScalarEvolution &se, LoopInfo &li) : SE(se), LI(li) {} - - LoopInfo &getLoopInfo() const { return LI; } + explicit SCEVExpander(ScalarEvolution &se) + : SE(se) {} /// clear - Erase the contents of the InsertedExpressions map so that users /// trying to expand the same expression into multiple BasicBlocks or @@ -52,113 +47,93 @@ namespace llvm { /// inserted by the code rewriter. If so, the client should not modify the /// instruction. bool isInsertedInstruction(Instruction *I) const { - return InsertedInstructions.count(I); + return InsertedValues.count(I); + } + + /// isInsertedExpression - Return true if the the code rewriter has a + /// Value* recorded for the given expression. + bool isInsertedExpression(const SCEV *S) const { + return InsertedExpressions.count(S); } /// 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->isIntegral() || 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); - } + Value *getOrInsertCanonicalInductionVariable(const Loop *L, const Type *Ty); /// 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); + void addInsertedValue(Value *V, const SCEV *S) { + InsertedExpressions[S] = V; + InsertedValues.insert(V); } + void setInsertionPoint(BasicBlock::iterator NewIP) { InsertPt = NewIP; } + + BasicBlock::iterator getInsertionPoint() const { return InsertPt; } + + /// 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); + /// 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, + BasicBlock::iterator IP) { + setInsertionPoint(IP); + return expandCodeFor(SH, Ty); } /// InsertCastOfTo - Insert a cast of V to the specified type, doing what /// we can to share the casts. - static Value *InsertCastOfTo(Instruction::CastOps opcode, Value *V, - const Type *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; - - Value *V = visit(S); - InsertedExpressions[S] = V; - return V; - } + Value *InsertCastOfTo(Instruction::CastOps opcode, Value *V, + const Type *Ty); - Value *expandInTy(SCEV *S, const Type *Ty) { - Value *V = expand(S); - if (Ty && V->getType() != Ty) { - if (isa(Ty) && V->getType()->isIntegral()) - return InsertCastOfTo(Instruction::IntToPtr, V, Ty); - else if (Ty->isIntegral() && isa(V->getType())) - return InsertCastOfTo(Instruction::PtrToInt, V, Ty); - else if (Ty->getPrimitiveSizeInBits() == - V->getType()->getPrimitiveSizeInBits()) - return InsertCastOfTo(Instruction::BitCast, V, Ty); - else if (Ty->getPrimitiveSizeInBits() > - V->getType()->getPrimitiveSizeInBits()) - return InsertCastOfTo(Instruction::ZExt, V, Ty); - else - return InsertCastOfTo(Instruction::Trunc, V, Ty); - } - return V; - } + /// InsertNoopCastOfTo - Insert a cast of V to the specified type, + /// which must be possible with a noop cast. + Value *InsertNoopCastOfTo(Value *V, const Type *Ty); + + /// 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, BasicBlock::iterator InsertPt); - Value *visitConstant(SCEVConstant *S) { + private: + /// 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); + + Value *visitConstant(const SCEVConstant *S) { return S->getValue(); } - Value *visitTruncateExpr(SCEVTruncateExpr *S) { - Value *V = expand(S->getOperand()); - return CastInst::createTruncOrBitCast(V, S->getType(), "tmp.", InsertPt); - } + Value *visitTruncateExpr(const SCEVTruncateExpr *S); - Value *visitZeroExtendExpr(SCEVZeroExtendExpr *S) { - Value *V = expandInTy(S->getOperand(), S->getType()); - return CastInst::createZExtOrBitCast(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 *visitSDivExpr(SCEVSDivExpr *S) { - const Type *Ty = S->getType(); - Value *LHS = expandInTy(S->getLHS(), Ty); - Value *RHS = expandInTy(S->getRHS(), Ty); - return BinaryOperator::createSDiv(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(); } };