ScalarEvolutionExpander.cpp revision 890f92b744fb074465bc2b7006ee753a181f62a4
136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman//===- ScalarEvolutionExpander.cpp - Scalar Evolution Analysis --*- C++ -*-===// 236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman// 336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman// The LLVM Compiler Infrastructure 436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// 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" 182d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman#include "llvm/Target/TargetData.h" 1936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begemanusing namespace llvm; 2036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 21ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner/// InsertCastOfTo - Insert a cast of V to the specified type, doing what 22ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner/// we can to share the casts. 233ba68b9eef2851dae8a9d1b18928c6fa2e3c5f87Reid SpencerValue *SCEVExpander::InsertCastOfTo(Instruction::CastOps opcode, Value *V, 243ba68b9eef2851dae8a9d1b18928c6fa2e3c5f87Reid Spencer const Type *Ty) { 252d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman // Short-circuit unnecessary bitcasts. 262d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman if (opcode == Instruction::BitCast && V->getType() == Ty) 272d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman return V; 282d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman 29f04fa483b83227c570bc58e1684ea096430a6697Dan Gohman // Short-circuit unnecessary inttoptr<->ptrtoint casts. 30f04fa483b83227c570bc58e1684ea096430a6697Dan Gohman if (opcode == Instruction::PtrToInt && Ty == TD.getIntPtrType()) 31f04fa483b83227c570bc58e1684ea096430a6697Dan Gohman if (IntToPtrInst *ITP = dyn_cast<IntToPtrInst>(V)) 32f04fa483b83227c570bc58e1684ea096430a6697Dan Gohman return ITP->getOperand(0); 33f04fa483b83227c570bc58e1684ea096430a6697Dan Gohman if (opcode == Instruction::IntToPtr && V->getType() == TD.getIntPtrType()) 34f04fa483b83227c570bc58e1684ea096430a6697Dan Gohman if (PtrToIntInst *PTI = dyn_cast<PtrToIntInst>(V)) 35f04fa483b83227c570bc58e1684ea096430a6697Dan Gohman return PTI->getOperand(0); 36f04fa483b83227c570bc58e1684ea096430a6697Dan Gohman 37ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner // FIXME: keep track of the cast instruction. 38ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if (Constant *C = dyn_cast<Constant>(V)) 39d977d8651a5cd26a3e1088267f31cade405f2adfReid Spencer return ConstantExpr::getCast(opcode, C, Ty); 40ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner 41ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if (Argument *A = dyn_cast<Argument>(V)) { 42ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner // Check to see if there is already a cast! 43ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner for (Value::use_iterator UI = A->use_begin(), E = A->use_end(); 44ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner UI != E; ++UI) { 45ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if ((*UI)->getType() == Ty) 463913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (CastInst *CI = dyn_cast<CastInst>(cast<Instruction>(*UI))) 473913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (CI->getOpcode() == opcode) { 483913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz // If the cast isn't the first instruction of the function, move it. 493913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (BasicBlock::iterator(CI) != 503913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz A->getParent()->getEntryBlock().begin()) { 513913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz CI->moveBefore(A->getParent()->getEntryBlock().begin()); 523913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz } 533913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz return CI; 54ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 55ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 567cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif return CastInst::Create(opcode, V, Ty, V->getName(), 57d977d8651a5cd26a3e1088267f31cade405f2adfReid Spencer A->getParent()->getEntryBlock().begin()); 58ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 593913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz 60ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner Instruction *I = cast<Instruction>(V); 613913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz 62ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner // Check to see if there is already a cast. If there is, use it. 63ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 64ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner UI != E; ++UI) { 65ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if ((*UI)->getType() == Ty) 663913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (CastInst *CI = dyn_cast<CastInst>(cast<Instruction>(*UI))) 673913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (CI->getOpcode() == opcode) { 683913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz BasicBlock::iterator It = I; ++It; 693913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (isa<InvokeInst>(I)) 703913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz It = cast<InvokeInst>(I)->getNormalDest()->begin(); 713913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz while (isa<PHINode>(It)) ++It; 723913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (It != BasicBlock::iterator(CI)) { 733913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz // Splice the cast immediately after the operand in question. 743913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz CI->moveBefore(It); 753913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz } 763913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz return CI; 77ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 78ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 79ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner BasicBlock::iterator IP = I; ++IP; 80ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if (InvokeInst *II = dyn_cast<InvokeInst>(I)) 81ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner IP = II->getNormalDest()->begin(); 82ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner while (isa<PHINode>(IP)) ++IP; 837cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif return CastInst::Create(opcode, V, Ty, V->getName(), IP); 84ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner} 85ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner 867fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner/// InsertBinop - Insert the specified binary operator, doing a small amount 877fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner/// of work to avoid inserting an obviously redundant operation. 887fec90ebf4ebe7aa73a6dd7d275c255587c041adChris LattnerValue *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, 898a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz Value *RHS, Instruction *InsertPt) { 900f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman // Fold a binop with constant operands. 910f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman if (Constant *CLHS = dyn_cast<Constant>(LHS)) 920f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman if (Constant *CRHS = dyn_cast<Constant>(RHS)) 930f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman return ConstantExpr::get(Opcode, CLHS, CRHS); 940f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman 957fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner // Do a quick scan to see if we have this binop nearby. If so, reuse it. 967fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner unsigned ScanLimit = 6; 978a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz BasicBlock::iterator BlockBegin = InsertPt->getParent()->begin(); 988a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz if (InsertPt != BlockBegin) { 998a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz // Scanning starts from the last instruction before InsertPt. 1008a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz BasicBlock::iterator IP = InsertPt; 1018a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz --IP; 1028a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz for (; ScanLimit; --IP, --ScanLimit) { 1038a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(IP)) 1048a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz if (BinOp->getOpcode() == Opcode && BinOp->getOperand(0) == LHS && 1058a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz BinOp->getOperand(1) == RHS) 1068a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz return BinOp; 1078a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz if (IP == BlockBegin) break; 1088a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz } 1097fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner } 1108a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz 1118a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz // If we haven't found this binop, insert it. 1127cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif return BinaryOperator::Create(Opcode, LHS, RHS, "tmp", InsertPt); 1137fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner} 1147fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner 115890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitAddExpr(const SCEVAddExpr *S) { 1162d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman const Type *Ty = S->getType(); 1172d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman if (isa<PointerType>(Ty)) Ty = TD.getIntPtrType(); 118e24fa64d52330626553298f56ba5aa702624c282Dan Gohman Value *V = expand(S->getOperand(S->getNumOperands()-1)); 1192d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman V = InsertCastOfTo(CastInst::getCastOpcode(V, false, Ty, false), V, Ty); 120e24fa64d52330626553298f56ba5aa702624c282Dan Gohman 121e24fa64d52330626553298f56ba5aa702624c282Dan Gohman // Emit a bunch of add instructions 1222d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman for (int i = S->getNumOperands()-2; i >= 0; --i) { 1232d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman Value *W = expand(S->getOperand(i)); 1242d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman W = InsertCastOfTo(CastInst::getCastOpcode(W, false, Ty, false), W, Ty); 1252d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman V = InsertBinop(Instruction::Add, V, W, InsertPt); 1262d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman } 127e24fa64d52330626553298f56ba5aa702624c282Dan Gohman return V; 128e24fa64d52330626553298f56ba5aa702624c282Dan Gohman} 129e24fa64d52330626553298f56ba5aa702624c282Dan Gohman 130890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) { 1312d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman const Type *Ty = S->getType(); 1322d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman if (isa<PointerType>(Ty)) Ty = TD.getIntPtrType(); 13336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman int FirstOp = 0; // Set if we should emit a subtract. 134890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getOperand(0))) 13536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman if (SC->getValue()->isAllOnesValue()) 13636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman FirstOp = 1; 13736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 13836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman int i = S->getNumOperands()-2; 139d19534add90a2a894af61523b830887097bb780bDan Gohman Value *V = expand(S->getOperand(i+1)); 1402d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman V = InsertCastOfTo(CastInst::getCastOpcode(V, false, Ty, false), V, Ty); 14136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 14236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // Emit a bunch of multiply instructions 1432d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman for (; i >= FirstOp; --i) { 1442d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman Value *W = expand(S->getOperand(i)); 1452d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman W = InsertCastOfTo(CastInst::getCastOpcode(W, false, Ty, false), W, Ty); 1462d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman V = InsertBinop(Instruction::Mul, V, W, InsertPt); 1472d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman } 1482d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman 14936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // -1 * ... ---> 0 - ... 15036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman if (FirstOp == 1) 1512d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman V = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), V, InsertPt); 15236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman return V; 15336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman} 15436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 155890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitUDivExpr(const SCEVUDivExpr *S) { 1562d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman const Type *Ty = S->getType(); 1572d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman if (isa<PointerType>(Ty)) Ty = TD.getIntPtrType(); 1582d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman 1596177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky Value *LHS = expand(S->getLHS()); 1602d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman LHS = InsertCastOfTo(CastInst::getCastOpcode(LHS, false, Ty, false), LHS, Ty); 161890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getRHS())) { 1626177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky const APInt &RHS = SC->getValue()->getValue(); 1636177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky if (RHS.isPowerOf2()) 1646177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky return InsertBinop(Instruction::LShr, LHS, 1652d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman ConstantInt::get(Ty, RHS.logBase2()), 1666177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky InsertPt); 1676177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky } 1686177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky 1696177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky Value *RHS = expand(S->getRHS()); 1702d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman RHS = InsertCastOfTo(CastInst::getCastOpcode(RHS, false, Ty, false), RHS, Ty); 1716177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky return InsertBinop(Instruction::UDiv, LHS, RHS, InsertPt); 1726177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky} 1736177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky 174890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) { 17536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman const Type *Ty = S->getType(); 17636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman const Loop *L = S->getLoop(); 17736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // We cannot yet do fp recurrences, e.g. the xform of {X,+,F} --> X+{0,+,F} 1782d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman assert((Ty->isInteger() || isa<PointerType>(Ty)) && 1792d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman "Cannot expand fp recurrences yet!"); 18036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 18136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // {X,+,F} --> X + {0,+,F} 182cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman if (!S->getStart()->isZero()) { 183d19534add90a2a894af61523b830887097bb780bDan Gohman Value *Start = expand(S->getStart()); 1842d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman if (isa<PointerType>(Start->getType())) 1852d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman Start = InsertCastOfTo(Instruction::PtrToInt, Start, TD.getIntPtrType()); 18636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman std::vector<SCEVHandle> NewOps(S->op_begin(), S->op_end()); 187246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman NewOps[0] = SE.getIntegerSCEV(0, Ty); 188246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Value *Rest = expand(SE.getAddRecExpr(NewOps, L)); 1892d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman if (isa<PointerType>(Rest->getType())) 1902d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman Rest = InsertCastOfTo(Instruction::PtrToInt, Rest, TD.getIntPtrType()); 19136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 19236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // FIXME: look for an existing add to use. 1937fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner return InsertBinop(Instruction::Add, Rest, Start, InsertPt); 19436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman } 19536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 19636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // {0,+,1} --> Insert a canonical induction variable into the loop! 19717f1972c770dc18f5c7c3c95776b4d62ae9e121dDan Gohman if (S->isAffine() && 198246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman S->getOperand(1) == SE.getIntegerSCEV(1, Ty)) { 19936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // Create and insert the PHI node for the induction variable in the 20036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // specified loop. 20136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman BasicBlock *Header = L->getHeader(); 202051a950000e21935165db56695e35bade668193bGabor Greif PHINode *PN = PHINode::Create(Ty, "indvar", Header->begin()); 20336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman PN->addIncoming(Constant::getNullValue(Ty), L->getLoopPreheader()); 20436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 20536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman pred_iterator HPI = pred_begin(Header); 20636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman assert(HPI != pred_end(Header) && "Loop with zero preds???"); 20736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman if (!L->contains(*HPI)) ++HPI; 20836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman assert(HPI != pred_end(Header) && L->contains(*HPI) && 20936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman "No backedge in loop?"); 21036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 21136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // Insert a unit add instruction right before the terminator corresponding 21236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // to the back-edge. 21324d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer Constant *One = ConstantInt::get(Ty, 1); 2147cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Instruction *Add = BinaryOperator::CreateAdd(PN, One, "indvar.next", 21536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman (*HPI)->getTerminator()); 21636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 21736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman pred_iterator PI = pred_begin(Header); 21836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman if (*PI == L->getLoopPreheader()) 21936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman ++PI; 22036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman PN->addIncoming(Add, *PI); 22136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman return PN; 22236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman } 22336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 22436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // Get the canonical induction variable I for this loop. 22536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman Value *I = getOrInsertCanonicalInductionVariable(L, Ty); 22636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 227df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // If this is a simple linear addrec, emit it now as a special case. 22817f1972c770dc18f5c7c3c95776b4d62ae9e121dDan Gohman if (S->isAffine()) { // {0,+,F} --> i*F 229d19534add90a2a894af61523b830887097bb780bDan Gohman Value *F = expand(S->getOperand(1)); 2304d177592f265ec5cc1148bd2c35f4b268c4956c4Dan Gohman if (isa<PointerType>(F->getType())) 2314d177592f265ec5cc1148bd2c35f4b268c4956c4Dan Gohman F = InsertCastOfTo(Instruction::PtrToInt, F, TD.getIntPtrType()); 232df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner 233df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // IF the step is by one, just return the inserted IV. 2346b6b6ef1677fa71b1072c2911b4c1f9524a558c9Zhou Sheng if (ConstantInt *CI = dyn_cast<ConstantInt>(F)) 2354d050d73210d15d8a86ee5967c417ddb5bee4543Reid Spencer if (CI->getValue() == 1) 236df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner return I; 237df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner 238df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // If the insert point is directly inside of the loop, emit the multiply at 239df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // the insert point. Otherwise, L is a loop that is a parent of the insert 240df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // point loop. If we can, move the multiply to the outer most loop that it 241df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // is safe to be in. 242df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner Instruction *MulInsertPt = InsertPt; 243df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner Loop *InsertPtLoop = LI.getLoopFor(MulInsertPt->getParent()); 244df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner if (InsertPtLoop != L && InsertPtLoop && 245df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner L->contains(InsertPtLoop->getHeader())) { 2465d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz do { 247df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // If we cannot hoist the multiply out of this loop, don't. 248df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner if (!InsertPtLoop->isLoopInvariant(F)) break; 249df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner 2505d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz BasicBlock *InsertPtLoopPH = InsertPtLoop->getLoopPreheader(); 2515d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz 2525d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz // If this loop hasn't got a preheader, we aren't able to hoist the 2535d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz // multiply. 2545d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz if (!InsertPtLoopPH) 2555d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz break; 2565d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz 2575d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz // Otherwise, move the insert point to the preheader. 2585d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz MulInsertPt = InsertPtLoopPH->getTerminator(); 259df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner InsertPtLoop = InsertPtLoop->getParentLoop(); 2605d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz } while (InsertPtLoop != L); 261df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner } 262df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner 2637fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner return InsertBinop(Instruction::Mul, I, F, MulInsertPt); 26436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman } 26536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 26636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // If this is a chain of recurrences, turn it into a closed form, using the 26736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // folders, then expandCodeFor the closed form. This allows the folders to 26836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // simplify the expression without having to build a bunch of special code 26936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // into this folder. 270246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle IH = SE.getUnknown(I); // Get I as a "symbolic" SCEV. 27136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 272246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle V = S->evaluateAtIteration(IH, SE); 273e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling //cerr << "Evaluated: " << *this << "\n to: " << *V << "\n"; 27436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 275d19534add90a2a894af61523b830887097bb780bDan Gohman return expand(V); 27636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman} 27796fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov 278890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitTruncateExpr(const SCEVTruncateExpr *S) { 27911f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman Value *V = expand(S->getOperand()); 2802d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman if (isa<PointerType>(V->getType())) 2812d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman V = InsertCastOfTo(Instruction::PtrToInt, V, TD.getIntPtrType()); 282e9324f360590793576d15d9e15c21a4c19ef8d1cGabor Greif return CastInst::CreateTruncOrBitCast(V, S->getType(), "tmp.", InsertPt); 28311f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman} 28411f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman 285890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitZeroExtendExpr(const SCEVZeroExtendExpr *S) { 2868170a6849ed370059676f94d8a00ae652873a394Dan Gohman const Type *Ty = S->getType(); 2878170a6849ed370059676f94d8a00ae652873a394Dan Gohman if (isa<PointerType>(Ty)) Ty = TD.getIntPtrType(); 28811f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman Value *V = expand(S->getOperand()); 2892d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman if (isa<PointerType>(V->getType())) 2902d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman V = InsertCastOfTo(Instruction::PtrToInt, V, TD.getIntPtrType()); 2918170a6849ed370059676f94d8a00ae652873a394Dan Gohman return CastInst::CreateZExtOrBitCast(V, Ty, "tmp.", InsertPt); 29211f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman} 29311f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman 294890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitSignExtendExpr(const SCEVSignExtendExpr *S) { 2958170a6849ed370059676f94d8a00ae652873a394Dan Gohman const Type *Ty = S->getType(); 2968170a6849ed370059676f94d8a00ae652873a394Dan Gohman if (isa<PointerType>(Ty)) Ty = TD.getIntPtrType(); 29711f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman Value *V = expand(S->getOperand()); 2982d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman if (isa<PointerType>(V->getType())) 2992d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman V = InsertCastOfTo(Instruction::PtrToInt, V, TD.getIntPtrType()); 3008170a6849ed370059676f94d8a00ae652873a394Dan Gohman return CastInst::CreateSExtOrBitCast(V, Ty, "tmp.", InsertPt); 30111f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman} 30211f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman 303890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitSMaxExpr(const SCEVSMaxExpr *S) { 3046524d3ab0e93cfaa1da4293428a5b0b4f106606dDan Gohman const Type *Ty = S->getType(); 305c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky Value *LHS = expand(S->getOperand(0)); 3066524d3ab0e93cfaa1da4293428a5b0b4f106606dDan Gohman LHS = InsertCastOfTo(CastInst::getCastOpcode(LHS, false, Ty, false), LHS, Ty); 307c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky for (unsigned i = 1; i < S->getNumOperands(); ++i) { 308c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky Value *RHS = expand(S->getOperand(i)); 3096524d3ab0e93cfaa1da4293428a5b0b4f106606dDan Gohman RHS = InsertCastOfTo(CastInst::getCastOpcode(RHS, false, Ty, false), 3106524d3ab0e93cfaa1da4293428a5b0b4f106606dDan Gohman RHS, Ty); 311c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky Value *ICmp = new ICmpInst(ICmpInst::ICMP_SGT, LHS, RHS, "tmp", InsertPt); 312051a950000e21935165db56695e35bade668193bGabor Greif LHS = SelectInst::Create(ICmp, LHS, RHS, "smax", InsertPt); 313c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky } 314c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky return LHS; 315c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky} 316c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky 317890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitUMaxExpr(const SCEVUMaxExpr *S) { 3186524d3ab0e93cfaa1da4293428a5b0b4f106606dDan Gohman const Type *Ty = S->getType(); 3193e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky Value *LHS = expand(S->getOperand(0)); 3206524d3ab0e93cfaa1da4293428a5b0b4f106606dDan Gohman LHS = InsertCastOfTo(CastInst::getCastOpcode(LHS, false, Ty, false), LHS, Ty); 3213e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky for (unsigned i = 1; i < S->getNumOperands(); ++i) { 3223e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky Value *RHS = expand(S->getOperand(i)); 3236524d3ab0e93cfaa1da4293428a5b0b4f106606dDan Gohman RHS = InsertCastOfTo(CastInst::getCastOpcode(RHS, false, Ty, false), 3246524d3ab0e93cfaa1da4293428a5b0b4f106606dDan Gohman RHS, Ty); 3253e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky Value *ICmp = new ICmpInst(ICmpInst::ICMP_UGT, LHS, RHS, "tmp", InsertPt); 326051a950000e21935165db56695e35bade668193bGabor Greif LHS = SelectInst::Create(ICmp, LHS, RHS, "umax", InsertPt); 3273e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky } 3283e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky return LHS; 3293e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky} 3303e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky 3312d1be87ee40a4a0241d94448173879d9df2bc5b3Dan GohmanValue *SCEVExpander::expandCodeFor(SCEVHandle SH, const Type *Ty, 3322d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman Instruction *IP) { 33311f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman // Expand the code for this SCEV. 3342d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman assert(TD.getTypeSizeInBits(Ty) == TD.getTypeSizeInBits(SH->getType()) && 3352d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman "non-trivial casts should be done with the SCEVs directly!"); 33611f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman this->InsertPt = IP; 3372d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman Value *V = expand(SH); 3382d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman return InsertCastOfTo(CastInst::getCastOpcode(V, false, Ty, false), V, Ty); 33911f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman} 34011f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman 341890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::expand(const SCEV *S) { 34296fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov // Check to see if we already expanded this. 34396fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov std::map<SCEVHandle, Value*>::iterator I = InsertedExpressions.find(S); 34496fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov if (I != InsertedExpressions.end()) 34596fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov return I->second; 34696fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov 34796fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov Value *V = visit(S); 34896fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov InsertedExpressions[S] = V; 34996fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov return V; 35096fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov} 351