ScalarEvolutionExpander.cpp revision 96fea337d27357e9b62abbf3d2d5ce29f1c8e870
136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman//===- ScalarEvolutionExpander.cpp - Scalar Evolution Analysis --*- C++ -*-===// 236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman// 336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman// The LLVM Compiler Infrastructure 436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman// 536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman// This file was developed by the LLVM research group and is distributed under 636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman// the University of Illinois Open Source License. See LICENSE.TXT for details. 736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman// 836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman//===----------------------------------------------------------------------===// 936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman// 1036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman// This file contains the implementation of the scalar evolution expander, 1136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman// which is used to generate the code corresponding to a given scalar evolution 1236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman// expression. 1336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman// 1436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman//===----------------------------------------------------------------------===// 1536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 1636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman#include "llvm/Analysis/ScalarEvolutionExpander.h" 17e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling#include "llvm/Analysis/LoopInfo.h" 1836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begemanusing namespace llvm; 1936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 20ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner/// InsertCastOfTo - Insert a cast of V to the specified type, doing what 21ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner/// we can to share the casts. 223ba68b9eef2851dae8a9d1b18928c6fa2e3c5f87Reid SpencerValue *SCEVExpander::InsertCastOfTo(Instruction::CastOps opcode, Value *V, 233ba68b9eef2851dae8a9d1b18928c6fa2e3c5f87Reid Spencer const Type *Ty) { 24ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner // FIXME: keep track of the cast instruction. 25ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if (Constant *C = dyn_cast<Constant>(V)) 26d977d8651a5cd26a3e1088267f31cade405f2adfReid Spencer return ConstantExpr::getCast(opcode, C, Ty); 27ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner 28ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if (Argument *A = dyn_cast<Argument>(V)) { 29ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner // Check to see if there is already a cast! 30ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner for (Value::use_iterator UI = A->use_begin(), E = A->use_end(); 31ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner UI != E; ++UI) { 32ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if ((*UI)->getType() == Ty) 33ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if (CastInst *CI = dyn_cast<CastInst>(cast<Instruction>(*UI))) { 343da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer // If the cast isn't the first instruction of the function, move it. 35ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if (BasicBlock::iterator(CI) != 36ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner A->getParent()->getEntryBlock().begin()) { 37ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner CI->moveBefore(A->getParent()->getEntryBlock().begin()); 38ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 39ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner return CI; 40ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 41ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 42d977d8651a5cd26a3e1088267f31cade405f2adfReid Spencer return CastInst::create(opcode, V, Ty, V->getName(), 43d977d8651a5cd26a3e1088267f31cade405f2adfReid Spencer A->getParent()->getEntryBlock().begin()); 44ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 45ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner 46ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner Instruction *I = cast<Instruction>(V); 47ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner 48ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner // Check to see if there is already a cast. If there is, use it. 49ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 50ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner UI != E; ++UI) { 51ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if ((*UI)->getType() == Ty) 52ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if (CastInst *CI = dyn_cast<CastInst>(cast<Instruction>(*UI))) { 53ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner BasicBlock::iterator It = I; ++It; 54ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if (isa<InvokeInst>(I)) 55ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner It = cast<InvokeInst>(I)->getNormalDest()->begin(); 56ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner while (isa<PHINode>(It)) ++It; 57ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if (It != BasicBlock::iterator(CI)) { 58ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner // Splice the cast immediately after the operand in question. 59ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner CI->moveBefore(It); 60ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 61ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner return CI; 62ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 63ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 64ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner BasicBlock::iterator IP = I; ++IP; 65ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if (InvokeInst *II = dyn_cast<InvokeInst>(I)) 66ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner IP = II->getNormalDest()->begin(); 67ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner while (isa<PHINode>(IP)) ++IP; 68d977d8651a5cd26a3e1088267f31cade405f2adfReid Spencer return CastInst::create(opcode, V, Ty, V->getName(), IP); 69ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner} 70ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner 717fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner/// InsertBinop - Insert the specified binary operator, doing a small amount 727fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner/// of work to avoid inserting an obviously redundant operation. 737fec90ebf4ebe7aa73a6dd7d275c255587c041adChris LattnerValue *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, 74b1b2f0bc44d01b33198a3aa51a64f79bad01378fChris Lattner Value *RHS, Instruction *&InsertPt) { 750f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman // Fold a binop with constant operands. 760f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman if (Constant *CLHS = dyn_cast<Constant>(LHS)) 770f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman if (Constant *CRHS = dyn_cast<Constant>(RHS)) 780f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman return ConstantExpr::get(Opcode, CLHS, CRHS); 790f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman 807fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner // Do a quick scan to see if we have this binop nearby. If so, reuse it. 817fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner unsigned ScanLimit = 6; 827fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner for (BasicBlock::iterator IP = InsertPt, E = InsertPt->getParent()->begin(); 837fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner ScanLimit; --IP, --ScanLimit) { 847fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(IP)) 857fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner if (BinOp->getOpcode() == Opcode && BinOp->getOperand(0) == LHS && 86b1b2f0bc44d01b33198a3aa51a64f79bad01378fChris Lattner BinOp->getOperand(1) == RHS) { 87b1b2f0bc44d01b33198a3aa51a64f79bad01378fChris Lattner // If we found the instruction *at* the insert point, insert later 88b1b2f0bc44d01b33198a3aa51a64f79bad01378fChris Lattner // instructions after it. 89b1b2f0bc44d01b33198a3aa51a64f79bad01378fChris Lattner if (BinOp == InsertPt) 90b1b2f0bc44d01b33198a3aa51a64f79bad01378fChris Lattner InsertPt = ++IP; 917fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner return BinOp; 92b1b2f0bc44d01b33198a3aa51a64f79bad01378fChris Lattner } 937fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner if (IP == E) break; 947fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner } 957fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner 967fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner // If we don't have 977fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner return BinaryOperator::create(Opcode, LHS, RHS, "tmp.", InsertPt); 987fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner} 997fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner 10036f891bdf6cf38fcc655a0930ca18664e18518d4Nate BegemanValue *SCEVExpander::visitMulExpr(SCEVMulExpr *S) { 10136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman int FirstOp = 0; // Set if we should emit a subtract. 10236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman if (SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getOperand(0))) 10336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman if (SC->getValue()->isAllOnesValue()) 10436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman FirstOp = 1; 10536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 10636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman int i = S->getNumOperands()-2; 107d19534add90a2a894af61523b830887097bb780bDan Gohman Value *V = expand(S->getOperand(i+1)); 10836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 10936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // Emit a bunch of multiply instructions 11036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman for (; i >= FirstOp; --i) 111d19534add90a2a894af61523b830887097bb780bDan Gohman V = InsertBinop(Instruction::Mul, V, expand(S->getOperand(i)), 1127fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner InsertPt); 11336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // -1 * ... ---> 0 - ... 11436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman if (FirstOp == 1) 1157fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner V = InsertBinop(Instruction::Sub, Constant::getNullValue(V->getType()), V, 1167fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner InsertPt); 11736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman return V; 11836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman} 11936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 12036f891bdf6cf38fcc655a0930ca18664e18518d4Nate BegemanValue *SCEVExpander::visitAddRecExpr(SCEVAddRecExpr *S) { 12136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman const Type *Ty = S->getType(); 12236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman const Loop *L = S->getLoop(); 12336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // We cannot yet do fp recurrences, e.g. the xform of {X,+,F} --> X+{0,+,F} 12442a75517250017a52afb03a0ade03cbd49559fe5Chris Lattner assert(Ty->isInteger() && "Cannot expand fp recurrences yet!"); 12536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 12636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // {X,+,F} --> X + {0,+,F} 12736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman if (!isa<SCEVConstant>(S->getStart()) || 128cae5754619433aed7be74abbf1c0551a82d369cbReid Spencer !cast<SCEVConstant>(S->getStart())->getValue()->isZero()) { 129d19534add90a2a894af61523b830887097bb780bDan Gohman Value *Start = expand(S->getStart()); 13036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman std::vector<SCEVHandle> NewOps(S->op_begin(), S->op_end()); 13136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman NewOps[0] = SCEVUnknown::getIntegerSCEV(0, Ty); 132d19534add90a2a894af61523b830887097bb780bDan Gohman Value *Rest = expand(SCEVAddRecExpr::get(NewOps, L)); 13336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 13436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // FIXME: look for an existing add to use. 1357fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner return InsertBinop(Instruction::Add, Rest, Start, InsertPt); 13636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman } 13736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 13836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // {0,+,1} --> Insert a canonical induction variable into the loop! 13936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman if (S->getNumOperands() == 2 && 14036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman S->getOperand(1) == SCEVUnknown::getIntegerSCEV(1, Ty)) { 14136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // Create and insert the PHI node for the induction variable in the 14236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // specified loop. 14336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman BasicBlock *Header = L->getHeader(); 14436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman PHINode *PN = new PHINode(Ty, "indvar", Header->begin()); 14536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman PN->addIncoming(Constant::getNullValue(Ty), L->getLoopPreheader()); 14636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 14736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman pred_iterator HPI = pred_begin(Header); 14836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman assert(HPI != pred_end(Header) && "Loop with zero preds???"); 14936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman if (!L->contains(*HPI)) ++HPI; 15036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman assert(HPI != pred_end(Header) && L->contains(*HPI) && 15136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman "No backedge in loop?"); 15236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 15336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // Insert a unit add instruction right before the terminator corresponding 15436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // to the back-edge. 15524d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer Constant *One = ConstantInt::get(Ty, 1); 15636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman Instruction *Add = BinaryOperator::createAdd(PN, One, "indvar.next", 15736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman (*HPI)->getTerminator()); 15836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 15936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman pred_iterator PI = pred_begin(Header); 16036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman if (*PI == L->getLoopPreheader()) 16136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman ++PI; 16236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman PN->addIncoming(Add, *PI); 16336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman return PN; 16436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman } 16536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 16636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // Get the canonical induction variable I for this loop. 16736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman Value *I = getOrInsertCanonicalInductionVariable(L, Ty); 16836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 169df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // If this is a simple linear addrec, emit it now as a special case. 17036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman if (S->getNumOperands() == 2) { // {0,+,F} --> i*F 171d19534add90a2a894af61523b830887097bb780bDan Gohman Value *F = expand(S->getOperand(1)); 172df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner 173df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // IF the step is by one, just return the inserted IV. 1746b6b6ef1677fa71b1072c2911b4c1f9524a558c9Zhou Sheng if (ConstantInt *CI = dyn_cast<ConstantInt>(F)) 1754d050d73210d15d8a86ee5967c417ddb5bee4543Reid Spencer if (CI->getValue() == 1) 176df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner return I; 177df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner 178df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // If the insert point is directly inside of the loop, emit the multiply at 179df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // the insert point. Otherwise, L is a loop that is a parent of the insert 180df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // point loop. If we can, move the multiply to the outer most loop that it 181df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // is safe to be in. 182df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner Instruction *MulInsertPt = InsertPt; 183df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner Loop *InsertPtLoop = LI.getLoopFor(MulInsertPt->getParent()); 184df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner if (InsertPtLoop != L && InsertPtLoop && 185df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner L->contains(InsertPtLoop->getHeader())) { 186df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner while (InsertPtLoop != L) { 187df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // If we cannot hoist the multiply out of this loop, don't. 188df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner if (!InsertPtLoop->isLoopInvariant(F)) break; 189df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner 190df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // Otherwise, move the insert point to the preheader of the loop. 191df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner MulInsertPt = InsertPtLoop->getLoopPreheader()->getTerminator(); 192df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner InsertPtLoop = InsertPtLoop->getParentLoop(); 193df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner } 194df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner } 195df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner 1967fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner return InsertBinop(Instruction::Mul, I, F, MulInsertPt); 19736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman } 19836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 19936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // If this is a chain of recurrences, turn it into a closed form, using the 20036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // folders, then expandCodeFor the closed form. This allows the folders to 20136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // simplify the expression without having to build a bunch of special code 20236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // into this folder. 20336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman SCEVHandle IH = SCEVUnknown::get(I); // Get I as a "symbolic" SCEV. 20436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 20536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman SCEVHandle V = S->evaluateAtIteration(IH); 206e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling //cerr << "Evaluated: " << *this << "\n to: " << *V << "\n"; 20736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 208d19534add90a2a894af61523b830887097bb780bDan Gohman return expand(V); 20936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman} 21096fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov 21196fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton KorobeynikovValue *SCEVExpander::expand(SCEV *S) { 21296fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov // Check to see if we already expanded this. 21396fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov std::map<SCEVHandle, Value*>::iterator I = InsertedExpressions.find(S); 21496fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov if (I != InsertedExpressions.end()) 21596fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov return I->second; 21696fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov 21796fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov Value *V = visit(S); 21896fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov InsertedExpressions[S] = V; 21996fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov return V; 22096fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov} 22196fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov 222