ScalarEvolutionExpander.cpp revision cf5ab820227dedd77fb91d0904b6dc3694a7c196
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" 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) { 242d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman // Short-circuit unnecessary bitcasts. 252d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman if (opcode == Instruction::BitCast && V->getType() == Ty) 262d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman return V; 272d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman 28f04fa483b83227c570bc58e1684ea096430a6697Dan Gohman // Short-circuit unnecessary inttoptr<->ptrtoint casts. 29af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman if ((opcode == Instruction::PtrToInt || opcode == Instruction::IntToPtr) && 3080dcdee0f48820ecea86c15768324945bb0d68d1Dan Gohman SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(V->getType())) { 31af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman if (CastInst *CI = dyn_cast<CastInst>(V)) 32af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman if ((CI->getOpcode() == Instruction::PtrToInt || 33af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman CI->getOpcode() == Instruction::IntToPtr) && 34af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman SE.getTypeSizeInBits(CI->getType()) == 35af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman SE.getTypeSizeInBits(CI->getOperand(0)->getType())) 36af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman return CI->getOperand(0); 3780dcdee0f48820ecea86c15768324945bb0d68d1Dan Gohman if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 3880dcdee0f48820ecea86c15768324945bb0d68d1Dan Gohman if ((CE->getOpcode() == Instruction::PtrToInt || 3980dcdee0f48820ecea86c15768324945bb0d68d1Dan Gohman CE->getOpcode() == Instruction::IntToPtr) && 4080dcdee0f48820ecea86c15768324945bb0d68d1Dan Gohman SE.getTypeSizeInBits(CE->getType()) == 4180dcdee0f48820ecea86c15768324945bb0d68d1Dan Gohman SE.getTypeSizeInBits(CE->getOperand(0)->getType())) 4280dcdee0f48820ecea86c15768324945bb0d68d1Dan Gohman return CE->getOperand(0); 4380dcdee0f48820ecea86c15768324945bb0d68d1Dan Gohman } 44f04fa483b83227c570bc58e1684ea096430a6697Dan Gohman 45ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner // FIXME: keep track of the cast instruction. 46ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if (Constant *C = dyn_cast<Constant>(V)) 47d977d8651a5cd26a3e1088267f31cade405f2adfReid Spencer return ConstantExpr::getCast(opcode, C, Ty); 48ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner 49ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if (Argument *A = dyn_cast<Argument>(V)) { 50ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner // Check to see if there is already a cast! 51ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner for (Value::use_iterator UI = A->use_begin(), E = A->use_end(); 52ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner UI != E; ++UI) { 53ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if ((*UI)->getType() == Ty) 543913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (CastInst *CI = dyn_cast<CastInst>(cast<Instruction>(*UI))) 553913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (CI->getOpcode() == opcode) { 563913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz // If the cast isn't the first instruction of the function, move it. 573913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (BasicBlock::iterator(CI) != 583913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz A->getParent()->getEntryBlock().begin()) { 59aabb04f52714ceb271dba7da18f757a4365bb4acDan Gohman // If the CastInst is the insert point, change the insert point. 60aabb04f52714ceb271dba7da18f757a4365bb4acDan Gohman if (CI == InsertPt) ++InsertPt; 61aabb04f52714ceb271dba7da18f757a4365bb4acDan Gohman // Splice the cast at the beginning of the entry block. 623913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz CI->moveBefore(A->getParent()->getEntryBlock().begin()); 633913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz } 643913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz return CI; 65ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 66ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 67cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *I = CastInst::Create(opcode, V, Ty, V->getName(), 68cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman A->getParent()->getEntryBlock().begin()); 69cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(I); 70cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman return I; 71ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 723913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz 73ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner Instruction *I = cast<Instruction>(V); 743913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz 75ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner // Check to see if there is already a cast. If there is, use it. 76ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 77ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner UI != E; ++UI) { 78ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if ((*UI)->getType() == Ty) 793913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (CastInst *CI = dyn_cast<CastInst>(cast<Instruction>(*UI))) 803913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (CI->getOpcode() == opcode) { 813913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz BasicBlock::iterator It = I; ++It; 823913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (isa<InvokeInst>(I)) 833913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz It = cast<InvokeInst>(I)->getNormalDest()->begin(); 843913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz while (isa<PHINode>(It)) ++It; 853913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (It != BasicBlock::iterator(CI)) { 86aabb04f52714ceb271dba7da18f757a4365bb4acDan Gohman // If the CastInst is the insert point, change the insert point. 87aabb04f52714ceb271dba7da18f757a4365bb4acDan Gohman if (CI == InsertPt) ++InsertPt; 883913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz // Splice the cast immediately after the operand in question. 893913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz CI->moveBefore(It); 903913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz } 913913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz return CI; 92ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 93ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 94ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner BasicBlock::iterator IP = I; ++IP; 95ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if (InvokeInst *II = dyn_cast<InvokeInst>(I)) 96ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner IP = II->getNormalDest()->begin(); 97ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner while (isa<PHINode>(IP)) ++IP; 98cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *CI = CastInst::Create(opcode, V, Ty, V->getName(), IP); 99cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(CI); 100cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman return CI; 101ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner} 102ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner 103af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman/// InsertNoopCastOfTo - Insert a cast of V to the specified type, 104af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman/// which must be possible with a noop cast. 105af79fb5f47b0088c6a8973a7fdbaea96973a429dDan GohmanValue *SCEVExpander::InsertNoopCastOfTo(Value *V, const Type *Ty) { 106af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman Instruction::CastOps Op = CastInst::getCastOpcode(V, false, Ty, false); 107af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman assert((Op == Instruction::BitCast || 108e2a17468d1e47ef430933b7a91c5c1c4669d7d8dDevang Patel Op == Instruction::PtrToInt || 109e2a17468d1e47ef430933b7a91c5c1c4669d7d8dDevang Patel Op == Instruction::IntToPtr) && 110af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman "InsertNoopCastOfTo cannot perform non-noop casts!"); 111af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman assert(SE.getTypeSizeInBits(V->getType()) == SE.getTypeSizeInBits(Ty) && 112af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman "InsertNoopCastOfTo cannot change sizes!"); 113af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman return InsertCastOfTo(Op, V, Ty); 114af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman} 115af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman 1167fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner/// InsertBinop - Insert the specified binary operator, doing a small amount 1177fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner/// of work to avoid inserting an obviously redundant operation. 1187fec90ebf4ebe7aa73a6dd7d275c255587c041adChris LattnerValue *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, 1196cdc727f2d7f68734526ef078f4632798ad40791Dan Gohman Value *RHS, BasicBlock::iterator InsertPt) { 1200f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman // Fold a binop with constant operands. 1210f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman if (Constant *CLHS = dyn_cast<Constant>(LHS)) 1220f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman if (Constant *CRHS = dyn_cast<Constant>(RHS)) 1230f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman return ConstantExpr::get(Opcode, CLHS, CRHS); 1240f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman 1257fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner // Do a quick scan to see if we have this binop nearby. If so, reuse it. 1267fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner unsigned ScanLimit = 6; 1278a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz BasicBlock::iterator BlockBegin = InsertPt->getParent()->begin(); 1288a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz if (InsertPt != BlockBegin) { 1298a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz // Scanning starts from the last instruction before InsertPt. 1308a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz BasicBlock::iterator IP = InsertPt; 1318a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz --IP; 1328a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz for (; ScanLimit; --IP, --ScanLimit) { 1338a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(IP)) 1348a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz if (BinOp->getOpcode() == Opcode && BinOp->getOperand(0) == LHS && 1358a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz BinOp->getOperand(1) == RHS) 1368a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz return BinOp; 1378a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz if (IP == BlockBegin) break; 1388a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz } 1397fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner } 1408a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz 1418a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz // If we haven't found this binop, insert it. 142cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *BO = BinaryOperator::Create(Opcode, LHS, RHS, "tmp", InsertPt); 143cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(BO); 144cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman return BO; 1457fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner} 1467fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner 147890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitAddExpr(const SCEVAddExpr *S) { 148af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 149e24fa64d52330626553298f56ba5aa702624c282Dan Gohman Value *V = expand(S->getOperand(S->getNumOperands()-1)); 150af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman V = InsertNoopCastOfTo(V, Ty); 151e24fa64d52330626553298f56ba5aa702624c282Dan Gohman 152e24fa64d52330626553298f56ba5aa702624c282Dan Gohman // Emit a bunch of add instructions 1532d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman for (int i = S->getNumOperands()-2; i >= 0; --i) { 1542d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman Value *W = expand(S->getOperand(i)); 155af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman W = InsertNoopCastOfTo(W, Ty); 1562d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman V = InsertBinop(Instruction::Add, V, W, InsertPt); 1572d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman } 158e24fa64d52330626553298f56ba5aa702624c282Dan Gohman return V; 159e24fa64d52330626553298f56ba5aa702624c282Dan Gohman} 160e24fa64d52330626553298f56ba5aa702624c282Dan Gohman 161890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) { 162af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 16336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman int FirstOp = 0; // Set if we should emit a subtract. 164890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getOperand(0))) 16536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman if (SC->getValue()->isAllOnesValue()) 16636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman FirstOp = 1; 16736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 16836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman int i = S->getNumOperands()-2; 169d19534add90a2a894af61523b830887097bb780bDan Gohman Value *V = expand(S->getOperand(i+1)); 170af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman V = InsertNoopCastOfTo(V, Ty); 17136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 17236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // Emit a bunch of multiply instructions 1732d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman for (; i >= FirstOp; --i) { 1742d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman Value *W = expand(S->getOperand(i)); 175af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman W = InsertNoopCastOfTo(W, Ty); 1762d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman V = InsertBinop(Instruction::Mul, V, W, InsertPt); 1772d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman } 1782d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman 17936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // -1 * ... ---> 0 - ... 18036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman if (FirstOp == 1) 1812d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman V = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), V, InsertPt); 18236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman return V; 18336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman} 18436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 185890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitUDivExpr(const SCEVUDivExpr *S) { 186af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 1872d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman 1886177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky Value *LHS = expand(S->getLHS()); 189af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman LHS = InsertNoopCastOfTo(LHS, Ty); 190890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getRHS())) { 1916177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky const APInt &RHS = SC->getValue()->getValue(); 1926177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky if (RHS.isPowerOf2()) 1936177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky return InsertBinop(Instruction::LShr, LHS, 1942d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman ConstantInt::get(Ty, RHS.logBase2()), 1956177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky InsertPt); 1966177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky } 1976177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky 1986177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky Value *RHS = expand(S->getRHS()); 199af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman RHS = InsertNoopCastOfTo(RHS, Ty); 2006177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky return InsertBinop(Instruction::UDiv, LHS, RHS, InsertPt); 2016177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky} 2026177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky 203890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) { 204af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 20536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman const Loop *L = S->getLoop(); 20636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 20736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // {X,+,F} --> X + {0,+,F} 208cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman if (!S->getStart()->isZero()) { 209d19534add90a2a894af61523b830887097bb780bDan Gohman Value *Start = expand(S->getStart()); 210af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman Start = InsertNoopCastOfTo(Start, Ty); 21136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman std::vector<SCEVHandle> NewOps(S->op_begin(), S->op_end()); 212246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman NewOps[0] = SE.getIntegerSCEV(0, Ty); 213246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman Value *Rest = expand(SE.getAddRecExpr(NewOps, L)); 214af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman Rest = InsertNoopCastOfTo(Rest, Ty); 21536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 21636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // FIXME: look for an existing add to use. 2177fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner return InsertBinop(Instruction::Add, Rest, Start, InsertPt); 21836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman } 21936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 22036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // {0,+,1} --> Insert a canonical induction variable into the loop! 22117f1972c770dc18f5c7c3c95776b4d62ae9e121dDan Gohman if (S->isAffine() && 222246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman S->getOperand(1) == SE.getIntegerSCEV(1, Ty)) { 22336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // Create and insert the PHI node for the induction variable in the 22436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // specified loop. 22536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman BasicBlock *Header = L->getHeader(); 226051a950000e21935165db56695e35bade668193bGabor Greif PHINode *PN = PHINode::Create(Ty, "indvar", Header->begin()); 227cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(PN); 22836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman PN->addIncoming(Constant::getNullValue(Ty), L->getLoopPreheader()); 22936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 23036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman pred_iterator HPI = pred_begin(Header); 23136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman assert(HPI != pred_end(Header) && "Loop with zero preds???"); 23236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman if (!L->contains(*HPI)) ++HPI; 23336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman assert(HPI != pred_end(Header) && L->contains(*HPI) && 23436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman "No backedge in loop?"); 23536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 23636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // Insert a unit add instruction right before the terminator corresponding 23736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // to the back-edge. 23824d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer Constant *One = ConstantInt::get(Ty, 1); 2397cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Instruction *Add = BinaryOperator::CreateAdd(PN, One, "indvar.next", 24036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman (*HPI)->getTerminator()); 241cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(Add); 24236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 24336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman pred_iterator PI = pred_begin(Header); 24436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman if (*PI == L->getLoopPreheader()) 24536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman ++PI; 24636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman PN->addIncoming(Add, *PI); 24736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman return PN; 24836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman } 24936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 25036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // Get the canonical induction variable I for this loop. 25136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman Value *I = getOrInsertCanonicalInductionVariable(L, Ty); 25236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 253df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // If this is a simple linear addrec, emit it now as a special case. 25417f1972c770dc18f5c7c3c95776b4d62ae9e121dDan Gohman if (S->isAffine()) { // {0,+,F} --> i*F 255d19534add90a2a894af61523b830887097bb780bDan Gohman Value *F = expand(S->getOperand(1)); 256af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman F = InsertNoopCastOfTo(F, Ty); 257df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner 258df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // IF the step is by one, just return the inserted IV. 2596b6b6ef1677fa71b1072c2911b4c1f9524a558c9Zhou Sheng if (ConstantInt *CI = dyn_cast<ConstantInt>(F)) 2604d050d73210d15d8a86ee5967c417ddb5bee4543Reid Spencer if (CI->getValue() == 1) 261df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner return I; 262df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner 263df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // If the insert point is directly inside of the loop, emit the multiply at 264df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // the insert point. Otherwise, L is a loop that is a parent of the insert 265df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // point loop. If we can, move the multiply to the outer most loop that it 266df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // is safe to be in. 2676cdc727f2d7f68734526ef078f4632798ad40791Dan Gohman BasicBlock::iterator MulInsertPt = getInsertionPoint(); 268df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner Loop *InsertPtLoop = LI.getLoopFor(MulInsertPt->getParent()); 269df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner if (InsertPtLoop != L && InsertPtLoop && 270df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner L->contains(InsertPtLoop->getHeader())) { 2715d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz do { 272df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // If we cannot hoist the multiply out of this loop, don't. 273df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner if (!InsertPtLoop->isLoopInvariant(F)) break; 274df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner 2755d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz BasicBlock *InsertPtLoopPH = InsertPtLoop->getLoopPreheader(); 2765d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz 2775d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz // If this loop hasn't got a preheader, we aren't able to hoist the 2785d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz // multiply. 2795d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz if (!InsertPtLoopPH) 2805d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz break; 2815d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz 2825d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz // Otherwise, move the insert point to the preheader. 2835d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz MulInsertPt = InsertPtLoopPH->getTerminator(); 284df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner InsertPtLoop = InsertPtLoop->getParentLoop(); 2855d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz } while (InsertPtLoop != L); 286df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner } 287df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner 2887fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner return InsertBinop(Instruction::Mul, I, F, MulInsertPt); 28936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman } 29036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 29136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // If this is a chain of recurrences, turn it into a closed form, using the 29236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // folders, then expandCodeFor the closed form. This allows the folders to 29336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // simplify the expression without having to build a bunch of special code 29436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // into this folder. 295246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle IH = SE.getUnknown(I); // Get I as a "symbolic" SCEV. 29636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 297246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle V = S->evaluateAtIteration(IH, SE); 298e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling //cerr << "Evaluated: " << *this << "\n to: " << *V << "\n"; 29936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 300d19534add90a2a894af61523b830887097bb780bDan Gohman return expand(V); 30136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman} 30296fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov 303890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitTruncateExpr(const SCEVTruncateExpr *S) { 304af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 30511f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman Value *V = expand(S->getOperand()); 306af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman V = InsertNoopCastOfTo(V, SE.getEffectiveSCEVType(V->getType())); 307cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *I = new TruncInst(V, Ty, "tmp.", InsertPt); 308cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(I); 309cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman return I; 31011f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman} 31111f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman 312890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitZeroExtendExpr(const SCEVZeroExtendExpr *S) { 313af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 31411f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman Value *V = expand(S->getOperand()); 315af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman V = InsertNoopCastOfTo(V, SE.getEffectiveSCEVType(V->getType())); 316cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *I = new ZExtInst(V, Ty, "tmp.", InsertPt); 317cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(I); 318cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman return I; 31911f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman} 32011f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman 321890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitSignExtendExpr(const SCEVSignExtendExpr *S) { 322af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 32311f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman Value *V = expand(S->getOperand()); 324af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman V = InsertNoopCastOfTo(V, SE.getEffectiveSCEVType(V->getType())); 325cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *I = new SExtInst(V, Ty, "tmp.", InsertPt); 326cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(I); 327cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman return I; 32811f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman} 32911f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman 330890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitSMaxExpr(const SCEVSMaxExpr *S) { 331af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 332c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky Value *LHS = expand(S->getOperand(0)); 333af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman LHS = InsertNoopCastOfTo(LHS, Ty); 334c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky for (unsigned i = 1; i < S->getNumOperands(); ++i) { 335c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky Value *RHS = expand(S->getOperand(i)); 336af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman RHS = InsertNoopCastOfTo(RHS, Ty); 337cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *ICmp = 338cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman new ICmpInst(ICmpInst::ICMP_SGT, LHS, RHS, "tmp", InsertPt); 339cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(ICmp); 340cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *Sel = SelectInst::Create(ICmp, LHS, RHS, "smax", InsertPt); 341cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(Sel); 342cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman LHS = Sel; 343c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky } 344c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky return LHS; 345c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky} 346c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky 347890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitUMaxExpr(const SCEVUMaxExpr *S) { 348af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 3493e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky Value *LHS = expand(S->getOperand(0)); 350af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman LHS = InsertNoopCastOfTo(LHS, Ty); 3513e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky for (unsigned i = 1; i < S->getNumOperands(); ++i) { 3523e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky Value *RHS = expand(S->getOperand(i)); 353af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman RHS = InsertNoopCastOfTo(RHS, Ty); 354cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *ICmp = 355cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman new ICmpInst(ICmpInst::ICMP_UGT, LHS, RHS, "tmp", InsertPt); 356cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(ICmp); 357cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *Sel = SelectInst::Create(ICmp, LHS, RHS, "umax", InsertPt); 358cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(Sel); 359cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman LHS = Sel; 3603e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky } 3613e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky return LHS; 3623e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky} 3633e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky 364752ec7da506f5d41c08bd37e195750b57550ce68Dan GohmanValue *SCEVExpander::expandCodeFor(SCEVHandle SH, const Type *Ty) { 36511f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman // Expand the code for this SCEV. 366af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman assert(SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType()) && 3672d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman "non-trivial casts should be done with the SCEVs directly!"); 3682d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman Value *V = expand(SH); 369af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman return InsertNoopCastOfTo(V, Ty); 37011f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman} 37111f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman 372890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::expand(const SCEV *S) { 37396fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov // Check to see if we already expanded this. 37496fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov std::map<SCEVHandle, Value*>::iterator I = InsertedExpressions.find(S); 37596fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov if (I != InsertedExpressions.end()) 37696fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov return I->second; 37796fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov 37896fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov Value *V = visit(S); 37996fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov InsertedExpressions[S] = V; 38096fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov return V; 38196fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov} 382