X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FScalarEvolutionExpander.cpp;h=30df087cef3e8bf42f1af09477366fd8cbf76658;hb=ef4cfc749a61d0d0252196c957697436ba7ec068;hp=3d985ab88525bd4e3c1fb7b059c38a9ef5db046c;hpb=24d6da5fedcf39891f7d8c5b031c01324b3db545;p=oota-llvm.git diff --git a/lib/Analysis/ScalarEvolutionExpander.cpp b/lib/Analysis/ScalarEvolutionExpander.cpp index 3d985ab8852..30df087cef3 100644 --- a/lib/Analysis/ScalarEvolutionExpander.cpp +++ b/lib/Analysis/ScalarEvolutionExpander.cpp @@ -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. // //===----------------------------------------------------------------------===// // @@ -30,64 +30,119 @@ Value *SCEVExpander::InsertCastOfTo(Instruction::CastOps opcode, Value *V, 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()); + if (CastInst *CI = dyn_cast(cast(*UI))) + if (CI->getOpcode() == opcode) { + // 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 CI; - } } - return CastInst::create(opcode, V, Ty, V->getName(), + 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); + if (CastInst *CI = dyn_cast(cast(*UI))) + if (CI->getOpcode() == opcode) { + 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; } - 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); + 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; + BasicBlock::iterator BlockBegin = InsertPt->getParent()->begin(); + if (InsertPt != BlockBegin) { + // Scanning starts from the last instruction before InsertPt. + BasicBlock::iterator IP = InsertPt; + --IP; + for (; ScanLimit; --IP, --ScanLimit) { + if (BinaryOperator *BinOp = dyn_cast(IP)) + if (BinOp->getOpcode() == Opcode && BinOp->getOperand(0) == LHS && + BinOp->getOperand(1) == RHS) + return BinOp; + if (IP == BlockBegin) break; + } + } + + // If we haven't found this binop, insert it. + return BinaryOperator::Create(Opcode, LHS, RHS, "tmp", InsertPt); } +Value *SCEVExpander::visitAddExpr(SCEVAddExpr *S) { + Value *V = expand(S->getOperand(S->getNumOperands()-1)); + + // Emit a bunch of add instructions + for (int i = S->getNumOperands()-2; i >= 0; --i) + V = InsertBinop(Instruction::Add, V, expand(S->getOperand(i)), + InsertPt); + return V; +} + 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; } +Value *SCEVExpander::visitUDivExpr(SCEVUDivExpr *S) { + Value *LHS = expand(S->getLHS()); + if (SCEVConstant *SC = dyn_cast(S->getRHS())) { + const APInt &RHS = SC->getValue()->getValue(); + if (RHS.isPowerOf2()) + return InsertBinop(Instruction::LShr, LHS, + ConstantInt::get(S->getType(), RHS.logBase2()), + InsertPt); + } + + Value *RHS = expand(S->getRHS()); + return InsertBinop(Instruction::UDiv, LHS, RHS, InsertPt); +} + Value *SCEVExpander::visitAddRecExpr(SCEVAddRecExpr *S) { const Type *Ty = S->getType(); const Loop *L = S->getLoop(); @@ -95,24 +150,23 @@ Value *SCEVExpander::visitAddRecExpr(SCEVAddRecExpr *S) { 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); + if (!S->getStart()->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); + NewOps[0] = SE.getIntegerSCEV(0, Ty); + Value *Rest = expand(SE.getAddRecExpr(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! - if (S->getNumOperands() == 2 && - S->getOperand(1) == SCEVUnknown::getIntegerSCEV(1, Ty)) { + if (S->isAffine() && + S->getOperand(1) == SE.getIntegerSCEV(1, Ty)) { // Create and insert the PHI node for the induction variable in the // specified loop. BasicBlock *Header = L->getHeader(); - PHINode *PN = new PHINode(Ty, "indvar", Header->begin()); + PHINode *PN = PHINode::Create(Ty, "indvar", Header->begin()); PN->addIncoming(Constant::getNullValue(Ty), L->getLoopPreheader()); pred_iterator HPI = pred_begin(Header); @@ -124,7 +178,7 @@ Value *SCEVExpander::visitAddRecExpr(SCEVAddRecExpr *S) { // Insert a unit add instruction right before the terminator corresponding // to the back-edge. Constant *One = ConstantInt::get(Ty, 1); - Instruction *Add = BinaryOperator::createAdd(PN, One, "indvar.next", + Instruction *Add = BinaryOperator::CreateAdd(PN, One, "indvar.next", (*HPI)->getTerminator()); pred_iterator PI = pred_begin(Header); @@ -138,12 +192,12 @@ Value *SCEVExpander::visitAddRecExpr(SCEVAddRecExpr *S) { Value *I = getOrInsertCanonicalInductionVariable(L, Ty); // 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); + if (S->isAffine()) { // {0,+,F} --> i*F + Value *F = expand(S->getOperand(1)); // IF the step is by one, just return the inserted IV. if (ConstantInt *CI = dyn_cast(F)) - if (CI->getZExtValue() == 1) + if (CI->getValue() == 1) return I; // If the insert point is directly inside of the loop, emit the multiply at @@ -154,27 +208,86 @@ Value *SCEVExpander::visitAddRecExpr(SCEVAddRecExpr *S) { Loop *InsertPtLoop = LI.getLoopFor(MulInsertPt->getParent()); if (InsertPtLoop != L && InsertPtLoop && L->contains(InsertPtLoop->getHeader())) { - while (InsertPtLoop != L) { + do { // If we cannot hoist the multiply out of this loop, don't. if (!InsertPtLoop->isLoopInvariant(F)) break; - // Otherwise, move the insert point to the preheader of the loop. - MulInsertPt = InsertPtLoop->getLoopPreheader()->getTerminator(); + BasicBlock *InsertPtLoopPH = InsertPtLoop->getLoopPreheader(); + + // If this loop hasn't got a preheader, we aren't able to hoist the + // multiply. + if (!InsertPtLoopPH) + break; + + // Otherwise, move the insert point to the preheader. + MulInsertPt = InsertPtLoopPH->getTerminator(); InsertPtLoop = InsertPtLoop->getParentLoop(); - } + } while (InsertPtLoop != L); } - 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 // folders, then expandCodeFor the closed form. This allows the folders to // simplify the expression without having to build a bunch of special code // into this folder. - SCEVHandle IH = SCEVUnknown::get(I); // Get I as a "symbolic" SCEV. + SCEVHandle IH = SE.getUnknown(I); // Get I as a "symbolic" SCEV. - SCEVHandle V = S->evaluateAtIteration(IH); + SCEVHandle V = S->evaluateAtIteration(IH, SE); //cerr << "Evaluated: " << *this << "\n to: " << *V << "\n"; - return expandInTy(V, Ty); + return expand(V); +} + +Value *SCEVExpander::visitTruncateExpr(SCEVTruncateExpr *S) { + Value *V = expand(S->getOperand()); + return CastInst::CreateTruncOrBitCast(V, S->getType(), "tmp.", InsertPt); +} + +Value *SCEVExpander::visitZeroExtendExpr(SCEVZeroExtendExpr *S) { + Value *V = expand(S->getOperand()); + return CastInst::CreateZExtOrBitCast(V, S->getType(), "tmp.", InsertPt); +} + +Value *SCEVExpander::visitSignExtendExpr(SCEVSignExtendExpr *S) { + Value *V = expand(S->getOperand()); + return CastInst::CreateSExtOrBitCast(V, S->getType(), "tmp.", InsertPt); +} + +Value *SCEVExpander::visitSMaxExpr(SCEVSMaxExpr *S) { + Value *LHS = expand(S->getOperand(0)); + for (unsigned i = 1; i < S->getNumOperands(); ++i) { + Value *RHS = expand(S->getOperand(i)); + Value *ICmp = new ICmpInst(ICmpInst::ICMP_SGT, LHS, RHS, "tmp", InsertPt); + LHS = SelectInst::Create(ICmp, LHS, RHS, "smax", InsertPt); + } + return LHS; +} + +Value *SCEVExpander::visitUMaxExpr(SCEVUMaxExpr *S) { + Value *LHS = expand(S->getOperand(0)); + for (unsigned i = 1; i < S->getNumOperands(); ++i) { + Value *RHS = expand(S->getOperand(i)); + Value *ICmp = new ICmpInst(ICmpInst::ICMP_UGT, LHS, RHS, "tmp", InsertPt); + LHS = SelectInst::Create(ICmp, LHS, RHS, "umax", InsertPt); + } + return LHS; +} + +Value *SCEVExpander::expandCodeFor(SCEVHandle SH, Instruction *IP) { + // Expand the code for this SCEV. + this->InsertPt = IP; + return expand(SH); +} + +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; }