X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FScalarEvolutionExpander.cpp;h=fc52fb70ff7baa90e450ce1a555aea80c60c322b;hb=68099d58cbad1fc6de980b2b01b6f221b560d5d5;hp=e2a98d4d862d76296eba4b0d2296c31869c10221;hpb=df14a04b5ccbbe6a46c2ccb93e27b12a36ff163e;p=oota-llvm.git diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp index e2a98d4d862..fc52fb70ff7 100644 --- a/lib/Analysis/ScalarEvolutionExpander.cpp +++ b/lib/Analysis/ScalarEvolutionExpander.cpp @@ -13,27 +13,107 @@ // //===----------------------------------------------------------------------===// -#include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/ScalarEvolutionExpander.h" +#include "llvm/Analysis/LoopInfo.h" using namespace llvm; +/// InsertCastOfTo - Insert a cast of V to the specified type, doing what +/// we can to share the casts. +Value *SCEVExpander::InsertCastOfTo(Instruction::CastOps opcode, Value *V, + const Type *Ty) { + // FIXME: keep track of the cast instruction. + if (Constant *C = dyn_cast(V)) + return ConstantExpr::getCast(opcode, C, Ty); + + if (Argument *A = dyn_cast(V)) { + // Check to see if there is already a cast! + for (Value::use_iterator UI = A->use_begin(), E = A->use_end(); + UI != E; ++UI) { + if ((*UI)->getType() == Ty) + if (CastInst *CI = dyn_cast(cast(*UI))) { + // If the cast isn't the first instruction of the function, move it. + if (BasicBlock::iterator(CI) != + A->getParent()->getEntryBlock().begin()) { + CI->moveBefore(A->getParent()->getEntryBlock().begin()); + } + return CI; + } + } + return CastInst::create(opcode, V, Ty, V->getName(), + A->getParent()->getEntryBlock().begin()); + } + + Instruction *I = 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. + CI->moveBefore(It); + } + return CI; + } + } + BasicBlock::iterator IP = I; ++IP; + if (InvokeInst *II = dyn_cast(I)) + IP = II->getNormalDest()->begin(); + while (isa(IP)) ++IP; + return CastInst::create(opcode, V, Ty, V->getName(), IP); +} + +/// InsertBinop - Insert the specified binary operator, doing a small amount +/// of work to avoid inserting an obviously redundant operation. +Value *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, + Value *RHS, Instruction *&InsertPt) { + // Fold a binop with constant operands. + if (Constant *CLHS = dyn_cast(LHS)) + if (Constant *CRHS = dyn_cast(RHS)) + return ConstantExpr::get(Opcode, CLHS, CRHS); + + // Do a quick scan to see if we have this binop nearby. If so, reuse it. + unsigned ScanLimit = 6; + for (BasicBlock::iterator IP = InsertPt, E = InsertPt->getParent()->begin(); + ScanLimit; --IP, --ScanLimit) { + if (BinaryOperator *BinOp = dyn_cast(IP)) + if (BinOp->getOpcode() == Opcode && BinOp->getOperand(0) == LHS && + BinOp->getOperand(1) == RHS) { + // If we found the instruction *at* the insert point, insert later + // instructions after it. + if (BinOp == InsertPt) + InsertPt = ++IP; + return BinOp; + } + if (IP == E) break; + } + + // If we don't have + return BinaryOperator::create(Opcode, LHS, RHS, "tmp", InsertPt); +} + Value *SCEVExpander::visitMulExpr(SCEVMulExpr *S) { - const Type *Ty = S->getType(); int FirstOp = 0; // Set if we should emit a subtract. if (SCEVConstant *SC = dyn_cast(S->getOperand(0))) if (SC->getValue()->isAllOnesValue()) FirstOp = 1; int i = S->getNumOperands()-2; - Value *V = expandInTy(S->getOperand(i+1), Ty); + Value *V = expand(S->getOperand(i+1)); // Emit a bunch of multiply instructions for (; i >= FirstOp; --i) - V = BinaryOperator::createMul(V, expandInTy(S->getOperand(i), Ty), - "tmp.", InsertPt); + V = InsertBinop(Instruction::Mul, V, expand(S->getOperand(i)), + InsertPt); // -1 * ... ---> 0 - ... if (FirstOp == 1) - V = BinaryOperator::createNeg(V, "tmp.", InsertPt); + V = InsertBinop(Instruction::Sub, Constant::getNullValue(V->getType()), V, + InsertPt); return V; } @@ -41,18 +121,18 @@ Value *SCEVExpander::visitAddRecExpr(SCEVAddRecExpr *S) { const Type *Ty = S->getType(); const Loop *L = S->getLoop(); // We cannot yet do fp recurrences, e.g. the xform of {X,+,F} --> X+{0,+,F} - assert(Ty->isIntegral() && "Cannot expand fp recurrences yet!"); + assert(Ty->isInteger() && "Cannot expand fp recurrences yet!"); // {X,+,F} --> X + {0,+,F} if (!isa(S->getStart()) || - !cast(S->getStart())->getValue()->isNullValue()) { - Value *Start = expandInTy(S->getStart(), Ty); + !cast(S->getStart())->getValue()->isZero()) { + Value *Start = expand(S->getStart()); std::vector NewOps(S->op_begin(), S->op_end()); NewOps[0] = SCEVUnknown::getIntegerSCEV(0, Ty); - Value *Rest = expandInTy(SCEVAddRecExpr::get(NewOps, L), Ty); + Value *Rest = expand(SCEVAddRecExpr::get(NewOps, L)); // FIXME: look for an existing add to use. - return BinaryOperator::createAdd(Rest, Start, "tmp.", InsertPt); + return InsertBinop(Instruction::Add, Rest, Start, InsertPt); } // {0,+,1} --> Insert a canonical induction variable into the loop! @@ -72,8 +152,7 @@ Value *SCEVExpander::visitAddRecExpr(SCEVAddRecExpr *S) { // Insert a unit add instruction right before the terminator corresponding // to the back-edge. - Constant *One = Ty->isFloatingPoint() ? (Constant*)ConstantFP::get(Ty, 1.0) - : ConstantInt::get(Ty, 1); + Constant *One = ConstantInt::get(Ty, 1); Instruction *Add = BinaryOperator::createAdd(PN, One, "indvar.next", (*HPI)->getTerminator()); @@ -89,11 +168,11 @@ Value *SCEVExpander::visitAddRecExpr(SCEVAddRecExpr *S) { // If this is a simple linear addrec, emit it now as a special case. if (S->getNumOperands() == 2) { // {0,+,F} --> i*F - Value *F = expandInTy(S->getOperand(1), Ty); + Value *F = expand(S->getOperand(1)); // IF the step is by one, just return the inserted IV. - if (ConstantIntegral *CI = dyn_cast(F)) - if (CI->getRawValue() == 1) + if (ConstantInt *CI = dyn_cast(F)) + if (CI->getValue() == 1) return I; // If the insert point is directly inside of the loop, emit the multiply at @@ -114,7 +193,7 @@ Value *SCEVExpander::visitAddRecExpr(SCEVAddRecExpr *S) { } } - return BinaryOperator::createMul(I, F, "tmp.", MulInsertPt); + return InsertBinop(Instruction::Mul, I, F, MulInsertPt); } // If this is a chain of recurrences, turn it into a closed form, using the @@ -124,7 +203,19 @@ Value *SCEVExpander::visitAddRecExpr(SCEVAddRecExpr *S) { SCEVHandle IH = SCEVUnknown::get(I); // Get I as a "symbolic" SCEV. SCEVHandle V = S->evaluateAtIteration(IH); - //std::cerr << "Evaluated: " << *this << "\n to: " << *V << "\n"; + //cerr << "Evaluated: " << *this << "\n to: " << *V << "\n"; - return expandInTy(V, Ty); + return expand(V); } + +Value *SCEVExpander::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; +} +