ScalarEvolutionExpander.cpp revision 4d8414f42033a5e744e8e60d2ca188b424c76168
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" 185be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman#include "llvm/Target/TargetData.h" 194d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman#include "llvm/ADT/STLExtras.h" 2036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begemanusing namespace llvm; 2136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 22ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner/// InsertCastOfTo - Insert a cast of V to the specified type, doing what 23ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner/// we can to share the casts. 243ba68b9eef2851dae8a9d1b18928c6fa2e3c5f87Reid SpencerValue *SCEVExpander::InsertCastOfTo(Instruction::CastOps opcode, Value *V, 253ba68b9eef2851dae8a9d1b18928c6fa2e3c5f87Reid Spencer const Type *Ty) { 262d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman // Short-circuit unnecessary bitcasts. 272d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman if (opcode == Instruction::BitCast && V->getType() == Ty) 282d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman return V; 292d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman 30f04fa483b83227c570bc58e1684ea096430a6697Dan Gohman // Short-circuit unnecessary inttoptr<->ptrtoint casts. 31af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman if ((opcode == Instruction::PtrToInt || opcode == Instruction::IntToPtr) && 3280dcdee0f48820ecea86c15768324945bb0d68d1Dan Gohman SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(V->getType())) { 33af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman if (CastInst *CI = dyn_cast<CastInst>(V)) 34af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman if ((CI->getOpcode() == Instruction::PtrToInt || 35af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman CI->getOpcode() == Instruction::IntToPtr) && 36af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman SE.getTypeSizeInBits(CI->getType()) == 37af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman SE.getTypeSizeInBits(CI->getOperand(0)->getType())) 38af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman return CI->getOperand(0); 3980dcdee0f48820ecea86c15768324945bb0d68d1Dan Gohman if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 4080dcdee0f48820ecea86c15768324945bb0d68d1Dan Gohman if ((CE->getOpcode() == Instruction::PtrToInt || 4180dcdee0f48820ecea86c15768324945bb0d68d1Dan Gohman CE->getOpcode() == Instruction::IntToPtr) && 4280dcdee0f48820ecea86c15768324945bb0d68d1Dan Gohman SE.getTypeSizeInBits(CE->getType()) == 4380dcdee0f48820ecea86c15768324945bb0d68d1Dan Gohman SE.getTypeSizeInBits(CE->getOperand(0)->getType())) 4480dcdee0f48820ecea86c15768324945bb0d68d1Dan Gohman return CE->getOperand(0); 4580dcdee0f48820ecea86c15768324945bb0d68d1Dan Gohman } 46f04fa483b83227c570bc58e1684ea096430a6697Dan Gohman 47ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner // FIXME: keep track of the cast instruction. 48ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if (Constant *C = dyn_cast<Constant>(V)) 49d977d8651a5cd26a3e1088267f31cade405f2adfReid Spencer return ConstantExpr::getCast(opcode, C, Ty); 50ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner 51ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if (Argument *A = dyn_cast<Argument>(V)) { 52ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner // Check to see if there is already a cast! 53ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner for (Value::use_iterator UI = A->use_begin(), E = A->use_end(); 54ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner UI != E; ++UI) { 55ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if ((*UI)->getType() == Ty) 563913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (CastInst *CI = dyn_cast<CastInst>(cast<Instruction>(*UI))) 573913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (CI->getOpcode() == opcode) { 583913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz // If the cast isn't the first instruction of the function, move it. 593913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (BasicBlock::iterator(CI) != 603913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz A->getParent()->getEntryBlock().begin()) { 61aabb04f52714ceb271dba7da18f757a4365bb4acDan Gohman // If the CastInst is the insert point, change the insert point. 62aabb04f52714ceb271dba7da18f757a4365bb4acDan Gohman if (CI == InsertPt) ++InsertPt; 63aabb04f52714ceb271dba7da18f757a4365bb4acDan Gohman // Splice the cast at the beginning of the entry block. 643913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz CI->moveBefore(A->getParent()->getEntryBlock().begin()); 653913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz } 663913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz return CI; 67ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 68ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 69cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *I = CastInst::Create(opcode, V, Ty, V->getName(), 70cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman A->getParent()->getEntryBlock().begin()); 71cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(I); 72cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman return I; 73ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 743913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz 75ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner Instruction *I = cast<Instruction>(V); 763913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz 77ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner // Check to see if there is already a cast. If there is, use it. 78ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 79ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner UI != E; ++UI) { 80ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if ((*UI)->getType() == Ty) 813913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (CastInst *CI = dyn_cast<CastInst>(cast<Instruction>(*UI))) 823913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (CI->getOpcode() == opcode) { 833913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz BasicBlock::iterator It = I; ++It; 843913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (isa<InvokeInst>(I)) 853913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz It = cast<InvokeInst>(I)->getNormalDest()->begin(); 863913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz while (isa<PHINode>(It)) ++It; 873913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (It != BasicBlock::iterator(CI)) { 88aabb04f52714ceb271dba7da18f757a4365bb4acDan Gohman // If the CastInst is the insert point, change the insert point. 89aabb04f52714ceb271dba7da18f757a4365bb4acDan Gohman if (CI == InsertPt) ++InsertPt; 903913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz // Splice the cast immediately after the operand in question. 913913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz CI->moveBefore(It); 923913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz } 933913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz return CI; 94ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 95ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 96ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner BasicBlock::iterator IP = I; ++IP; 97ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if (InvokeInst *II = dyn_cast<InvokeInst>(I)) 98ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner IP = II->getNormalDest()->begin(); 99ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner while (isa<PHINode>(IP)) ++IP; 100cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *CI = CastInst::Create(opcode, V, Ty, V->getName(), IP); 101cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(CI); 102cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman return CI; 103ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner} 104ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner 105af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman/// InsertNoopCastOfTo - Insert a cast of V to the specified type, 106af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman/// which must be possible with a noop cast. 107af79fb5f47b0088c6a8973a7fdbaea96973a429dDan GohmanValue *SCEVExpander::InsertNoopCastOfTo(Value *V, const Type *Ty) { 108af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman Instruction::CastOps Op = CastInst::getCastOpcode(V, false, Ty, false); 109af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman assert((Op == Instruction::BitCast || 110e2a17468d1e47ef430933b7a91c5c1c4669d7d8dDevang Patel Op == Instruction::PtrToInt || 111e2a17468d1e47ef430933b7a91c5c1c4669d7d8dDevang Patel Op == Instruction::IntToPtr) && 112af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman "InsertNoopCastOfTo cannot perform non-noop casts!"); 113af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman assert(SE.getTypeSizeInBits(V->getType()) == SE.getTypeSizeInBits(Ty) && 114af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman "InsertNoopCastOfTo cannot change sizes!"); 115af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman return InsertCastOfTo(Op, V, Ty); 116af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman} 117af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman 1187fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner/// InsertBinop - Insert the specified binary operator, doing a small amount 1197fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner/// of work to avoid inserting an obviously redundant operation. 1207fec90ebf4ebe7aa73a6dd7d275c255587c041adChris LattnerValue *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, 1216cdc727f2d7f68734526ef078f4632798ad40791Dan Gohman Value *RHS, BasicBlock::iterator InsertPt) { 1220f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman // Fold a binop with constant operands. 1230f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman if (Constant *CLHS = dyn_cast<Constant>(LHS)) 1240f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman if (Constant *CRHS = dyn_cast<Constant>(RHS)) 1250f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman return ConstantExpr::get(Opcode, CLHS, CRHS); 1260f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman 1277fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner // Do a quick scan to see if we have this binop nearby. If so, reuse it. 1287fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner unsigned ScanLimit = 6; 1298a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz BasicBlock::iterator BlockBegin = InsertPt->getParent()->begin(); 1308a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz if (InsertPt != BlockBegin) { 1318a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz // Scanning starts from the last instruction before InsertPt. 1328a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz BasicBlock::iterator IP = InsertPt; 1338a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz --IP; 1348a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz for (; ScanLimit; --IP, --ScanLimit) { 1355be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (IP->getOpcode() == (unsigned)Opcode && IP->getOperand(0) == LHS && 1365be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman IP->getOperand(1) == RHS) 1375be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman return IP; 1388a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz if (IP == BlockBegin) break; 1398a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz } 1407fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner } 1418a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz 1428a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz // If we haven't found this binop, insert it. 143cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *BO = BinaryOperator::Create(Opcode, LHS, RHS, "tmp", InsertPt); 144cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(BO); 145cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman return BO; 1467fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner} 1477fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner 1484a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman/// FactorOutConstant - Test if S is divisible by Factor, using signed 149453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// division. If so, update S with Factor divided out and return true. 1504a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman/// S need not be evenly divisble if a reasonable remainder can be 1514a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman/// computed. 152453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// TODO: When ScalarEvolution gets a SCEVSDivExpr, this can be made 153453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// unnecessary; in its place, just signed-divide Ops[i] by the scale and 154453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// check to see if the divide was folded. 155453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohmanstatic bool FactorOutConstant(SCEVHandle &S, 1564a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman SCEVHandle &Remainder, 157453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman const APInt &Factor, 158453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman ScalarEvolution &SE) { 159453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // Everything is divisible by one. 160453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (Factor == 1) 161453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman return true; 162453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman 163453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // For a Constant, check for a multiple of the given factor. 1644a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) { 1654a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman ConstantInt *CI = 1664a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman ConstantInt::get(C->getValue()->getValue().sdiv(Factor)); 1674a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman // If the quotient is zero and the remainder is non-zero, reject 1684a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman // the value at this scale. It will be considered for subsequent 1694a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman // smaller scales. 1704a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman if (C->isZero() || !CI->isZero()) { 171453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman SCEVHandle Div = SE.getConstant(CI); 172453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman S = Div; 1734a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman Remainder = 1744a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman SE.getAddExpr(Remainder, 1754a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman SE.getConstant(C->getValue()->getValue().srem(Factor))); 176453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman return true; 177453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 1784a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman } 179453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman 180453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // In a Mul, check if there is a constant operand which is a multiple 181453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // of the given factor. 182453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) 183453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (const SCEVConstant *C = dyn_cast<SCEVConstant>(M->getOperand(0))) 184453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (!C->getValue()->getValue().srem(Factor)) { 185453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman std::vector<SCEVHandle> NewMulOps(M->getOperands()); 186453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman NewMulOps[0] = 187453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman SE.getConstant(C->getValue()->getValue().sdiv(Factor)); 188453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman S = SE.getMulExpr(NewMulOps); 189453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman return true; 190453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 191453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman 192453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // In an AddRec, check if both start and step are divisible. 193453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) { 194453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman SCEVHandle Step = A->getStepRecurrence(SE); 1954a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman SCEVHandle StepRem = SE.getIntegerSCEV(0, Step->getType()); 1964a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman if (!FactorOutConstant(Step, StepRem, Factor, SE)) 1974a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman return false; 1984a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman if (!StepRem->isZero()) 1994a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman return false; 2004a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman SCEVHandle Start = A->getStart(); 2014a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman if (!FactorOutConstant(Start, Remainder, Factor, SE)) 202453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman return false; 203453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman S = SE.getAddRecExpr(Start, Step, A->getLoop()); 204453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman return true; 205453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 206453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman 207453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman return false; 208453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman} 209453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman 2105be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman/// expandAddToGEP - Expand a SCEVAddExpr with a pointer type into a GEP 211453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// instead of using ptrtoint+arithmetic+inttoptr. This helps 212453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// BasicAliasAnalysis analyze the result. However, it suffers from the 213453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// underlying bug described in PR2831. Addition in LLVM currently always 214453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// has two's complement wrapping guaranteed. However, the semantics for 215453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// getelementptr overflow are ambiguous. In the common case though, this 216453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// expansion gets used when a GEP in the original code has been converted 217453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// into integer arithmetic, in which case the resulting code will be no 218453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// more undefined than it was originally. 219453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// 220453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// Design note: It might seem desirable for this function to be more 221453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// loop-aware. If some of the indices are loop-invariant while others 222453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// aren't, it might seem desirable to emit multiple GEPs, keeping the 223453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// loop-invariant portions of the overall computation outside the loop. 224453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// However, there are a few reasons this is not done here. Hoisting simple 225453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// arithmetic is a low-level optimization that often isn't very 226453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// important until late in the optimization process. In fact, passes 227453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// like InstructionCombining will combine GEPs, even if it means 228453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// pushing loop-invariant computation down into loops, so even if the 229453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// GEPs were split here, the work would quickly be undone. The 230453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// LoopStrengthReduction pass, which is usually run quite late (and 231453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// after the last InstructionCombining pass), takes care of hoisting 232453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// loop-invariant portions of expressions, after considering what 233453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// can be folded using target addressing modes. 234453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// 235453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan GohmanValue *SCEVExpander::expandAddToGEP(const SCEVHandle *op_begin, 236453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman const SCEVHandle *op_end, 2375be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman const PointerType *PTy, 2385be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman const Type *Ty, 2395be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Value *V) { 2405be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman const Type *ElTy = PTy->getElementType(); 2415be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman SmallVector<Value *, 4> GepIndices; 242453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman std::vector<SCEVHandle> Ops(op_begin, op_end); 2435be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman bool AnyNonZeroIndices = false; 2445be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 2455be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // Decend down the pointer's type and attempt to convert the other 2465be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // operands into GEP indices, at each level. The first index in a GEP 2475be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // indexes into the array implied by the pointer operand; the rest of 2485be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // the indices index into the element or field type selected by the 2495be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // preceding index. 2505be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman for (;;) { 2515be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman APInt ElSize = APInt(SE.getTypeSizeInBits(Ty), 2525be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman ElTy->isSized() ? SE.TD->getTypeAllocSize(ElTy) : 0); 2535be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman std::vector<SCEVHandle> NewOps; 2545be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman std::vector<SCEVHandle> ScaledOps; 2555be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 256453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // Split AddRecs up into parts as either of the parts may be usable 257453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // without the other. 258453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Ops[i])) 259453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (!A->getStart()->isZero()) { 260453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman SCEVHandle Start = A->getStart(); 261453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman Ops.push_back(SE.getAddRecExpr(SE.getIntegerSCEV(0, A->getType()), 262453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman A->getStepRecurrence(SE), 263453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman A->getLoop())); 264453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman Ops[i] = Start; 265453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman ++e; 266453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 267453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // If the scale size is not 0, attempt to factor out a scale. 2685be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (ElSize != 0) { 269453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman SCEVHandle Op = Ops[i]; 2704a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman SCEVHandle Remainder = SE.getIntegerSCEV(0, Op->getType()); 2714a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman if (FactorOutConstant(Op, Remainder, ElSize, SE)) { 272453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman ScaledOps.push_back(Op); // Op now has ElSize factored out. 2734a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman NewOps.push_back(Remainder); 2745be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman continue; 2755be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 2765be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 277453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // If the operand was not divisible, add it to the list of operands 278453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // we'll scan next iteration. 2795be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman NewOps.push_back(Ops[i]); 2805be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 2815be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Ops = NewOps; 2825be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman AnyNonZeroIndices |= !ScaledOps.empty(); 2835be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Value *Scaled = ScaledOps.empty() ? 2845be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Constant::getNullValue(Ty) : 2855be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman expandCodeFor(SE.getAddExpr(ScaledOps), Ty); 2865be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman GepIndices.push_back(Scaled); 2875be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 2885be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // Collect struct field index operands. 2895be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (!Ops.empty()) 2905be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman while (const StructType *STy = dyn_cast<StructType>(ElTy)) { 2915be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[0])) 2925be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (SE.getTypeSizeInBits(C->getType()) <= 64) { 2935be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman const StructLayout &SL = *SE.TD->getStructLayout(STy); 2945be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman uint64_t FullOffset = C->getValue()->getZExtValue(); 2955be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (FullOffset < SL.getSizeInBytes()) { 2965be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman unsigned ElIdx = SL.getElementContainingOffset(FullOffset); 2975be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman GepIndices.push_back(ConstantInt::get(Type::Int32Ty, ElIdx)); 2985be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman ElTy = STy->getTypeAtIndex(ElIdx); 2995be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Ops[0] = 3005be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman SE.getConstant(ConstantInt::get(Ty, 3015be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman FullOffset - 3025be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman SL.getElementOffset(ElIdx))); 3035be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman AnyNonZeroIndices = true; 3045be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman continue; 3055be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 3065be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 3075be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman break; 3085be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 3095be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 3105be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (const ArrayType *ATy = dyn_cast<ArrayType>(ElTy)) { 3115be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman ElTy = ATy->getElementType(); 3125be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman continue; 3135be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 3145be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman break; 3155be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 3165be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 3175be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // If none of the operands were convertable to proper GEP indices, cast 3185be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // the base to i8* and do an ugly getelementptr with that. It's still 3195be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // better than ptrtoint+arithmetic+inttoptr at least. 3205be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (!AnyNonZeroIndices) { 3215be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman V = InsertNoopCastOfTo(V, 3225be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Type::Int8Ty->getPointerTo(PTy->getAddressSpace())); 32392fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *Idx = expandCodeFor(SE.getAddExpr(Ops), Ty); 3245be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 3255be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // Fold a GEP with constant operands. 3265be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (Constant *CLHS = dyn_cast<Constant>(V)) 3275be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (Constant *CRHS = dyn_cast<Constant>(Idx)) 328278b49af8a08f6ab6c486a3cfc7a9c1c1acd2b23Dan Gohman return ConstantExpr::getGetElementPtr(CLHS, &CRHS, 1); 3295be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 3305be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // Do a quick scan to see if we have this GEP nearby. If so, reuse it. 3315be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman unsigned ScanLimit = 6; 3325be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman BasicBlock::iterator BlockBegin = InsertPt->getParent()->begin(); 3335be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (InsertPt != BlockBegin) { 3345be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // Scanning starts from the last instruction before InsertPt. 3355be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman BasicBlock::iterator IP = InsertPt; 3365be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman --IP; 3375be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman for (; ScanLimit; --IP, --ScanLimit) { 3385be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (IP->getOpcode() == Instruction::GetElementPtr && 3395be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman IP->getOperand(0) == V && IP->getOperand(1) == Idx) 3405be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman return IP; 3415be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (IP == BlockBegin) break; 3425be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 3435be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 3445be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 3455be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Value *GEP = GetElementPtrInst::Create(V, Idx, "scevgep", InsertPt); 3465be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman InsertedValues.insert(GEP); 3475be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman return GEP; 3485be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 3495be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 3505be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // Insert a pretty getelementptr. 3515be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Value *GEP = GetElementPtrInst::Create(V, 3525be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman GepIndices.begin(), 3535be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman GepIndices.end(), 3545be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman "scevgep", InsertPt); 3555be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Ops.push_back(SE.getUnknown(GEP)); 3565be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman InsertedValues.insert(GEP); 3575be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman return expand(SE.getAddExpr(Ops)); 3585be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman} 3595be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 360890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitAddExpr(const SCEVAddExpr *S) { 361af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 362e24fa64d52330626553298f56ba5aa702624c282Dan Gohman Value *V = expand(S->getOperand(S->getNumOperands()-1)); 3635be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 364453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // Turn things like ptrtoint+arithmetic+inttoptr into GEP. See the 365453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // comments on expandAddToGEP for details. 3665be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (SE.TD) 367453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (const PointerType *PTy = dyn_cast<PointerType>(V->getType())) { 368453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman const std::vector<SCEVHandle> &Ops = S->getOperands(); 369fb5a3419f351056e0f599699d276bcab412d2cceDan Gohman return expandAddToGEP(&Ops[0], &Ops[Ops.size() - 1], 370453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman PTy, Ty, V); 371453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 3725be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 373af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman V = InsertNoopCastOfTo(V, Ty); 374e24fa64d52330626553298f56ba5aa702624c282Dan Gohman 375e24fa64d52330626553298f56ba5aa702624c282Dan Gohman // Emit a bunch of add instructions 3762d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman for (int i = S->getNumOperands()-2; i >= 0; --i) { 37792fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *W = expandCodeFor(S->getOperand(i), Ty); 3782d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman V = InsertBinop(Instruction::Add, V, W, InsertPt); 3792d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman } 380e24fa64d52330626553298f56ba5aa702624c282Dan Gohman return V; 381e24fa64d52330626553298f56ba5aa702624c282Dan Gohman} 3825be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 383890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) { 384af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 38536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman int FirstOp = 0; // Set if we should emit a subtract. 386890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getOperand(0))) 38736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman if (SC->getValue()->isAllOnesValue()) 38836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman FirstOp = 1; 38936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 39036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman int i = S->getNumOperands()-2; 39192fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *V = expandCodeFor(S->getOperand(i+1), Ty); 39236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 39336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // Emit a bunch of multiply instructions 3942d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman for (; i >= FirstOp; --i) { 39592fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *W = expandCodeFor(S->getOperand(i), Ty); 3962d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman V = InsertBinop(Instruction::Mul, V, W, InsertPt); 3972d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman } 3982d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman 39936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // -1 * ... ---> 0 - ... 40036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman if (FirstOp == 1) 4012d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman V = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), V, InsertPt); 40236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman return V; 40336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman} 40436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 405890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitUDivExpr(const SCEVUDivExpr *S) { 406af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 4072d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman 40892fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *LHS = expandCodeFor(S->getLHS(), Ty); 409890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getRHS())) { 4106177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky const APInt &RHS = SC->getValue()->getValue(); 4116177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky if (RHS.isPowerOf2()) 4126177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky return InsertBinop(Instruction::LShr, LHS, 4132d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman ConstantInt::get(Ty, RHS.logBase2()), 4146177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky InsertPt); 4156177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky } 4166177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky 41792fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *RHS = expandCodeFor(S->getRHS(), Ty); 4186177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky return InsertBinop(Instruction::UDiv, LHS, RHS, InsertPt); 4196177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky} 4206177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky 421453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// Move parts of Base into Rest to leave Base with the minimal 422453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// expression that provides a pointer operand suitable for a 423453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// GEP expansion. 424453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohmanstatic void ExposePointerBase(SCEVHandle &Base, SCEVHandle &Rest, 425453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman ScalarEvolution &SE) { 426453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman while (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Base)) { 427453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman Base = A->getStart(); 428453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman Rest = SE.getAddExpr(Rest, 429453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman SE.getAddRecExpr(SE.getIntegerSCEV(0, A->getType()), 430453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman A->getStepRecurrence(SE), 431453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman A->getLoop())); 432453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 433453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(Base)) { 434453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman Base = A->getOperand(A->getNumOperands()-1); 435453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman std::vector<SCEVHandle> NewAddOps(A->op_begin(), A->op_end()); 436453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman NewAddOps.back() = Rest; 437453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman Rest = SE.getAddExpr(NewAddOps); 438453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman ExposePointerBase(Base, Rest, SE); 439453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 440453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman} 441453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman 442890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) { 443af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 44436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman const Loop *L = S->getLoop(); 44536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 4464d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // First check for an existing canonical IV in a suitable type. 4474d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman PHINode *CanonicalIV = 0; 4484d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman if (PHINode *PN = L->getCanonicalInductionVariable()) 4494d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman if (SE.isSCEVable(PN->getType()) && 4504d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman isa<IntegerType>(SE.getEffectiveSCEVType(PN->getType())) && 4514d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman SE.getTypeSizeInBits(PN->getType()) >= SE.getTypeSizeInBits(Ty)) 4524d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman CanonicalIV = PN; 4534d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 4544d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // Rewrite an AddRec in terms of the canonical induction variable, if 4554d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // its type is more narrow. 4564d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman if (CanonicalIV && 4574d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman SE.getTypeSizeInBits(CanonicalIV->getType()) > 4584d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman SE.getTypeSizeInBits(Ty)) { 4594d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman SCEVHandle Start = SE.getAnyExtendExpr(S->getStart(), 4604d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman CanonicalIV->getType()); 4614d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman SCEVHandle Step = SE.getAnyExtendExpr(S->getStepRecurrence(SE), 4624d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman CanonicalIV->getType()); 4634d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman Value *V = expand(SE.getAddRecExpr(Start, Step, S->getLoop())); 4644d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman BasicBlock::iterator SaveInsertPt = getInsertionPoint(); 4654d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman BasicBlock::iterator NewInsertPt = 4664d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman next(BasicBlock::iterator(cast<Instruction>(V))); 4674d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman while (isa<PHINode>(NewInsertPt)) ++NewInsertPt; 4684d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman V = expandCodeFor(SE.getTruncateExpr(SE.getUnknown(V), Ty), 0, 4694d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman NewInsertPt); 4704d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman setInsertionPoint(SaveInsertPt); 4714d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman return V; 4724d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman } 4734d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 47436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // {X,+,F} --> X + {0,+,F} 475cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman if (!S->getStart()->isZero()) { 4765be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman std::vector<SCEVHandle> NewOps(S->getOperands()); 477246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman NewOps[0] = SE.getIntegerSCEV(0, Ty); 478453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman SCEVHandle Rest = SE.getAddRecExpr(NewOps, L); 479453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman 480453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // Turn things like ptrtoint+arithmetic+inttoptr into GEP. See the 481453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // comments on expandAddToGEP for details. 482453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (SE.TD) { 483453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman SCEVHandle Base = S->getStart(); 484f1a80489d6e9c76f52d9e6f59103a4fb2062e057Dan Gohman SCEVHandle RestArray[1] = { Rest }; 485453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // Dig into the expression to find the pointer base for a GEP. 486453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman ExposePointerBase(Base, RestArray[0], SE); 487453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // If we found a pointer, expand the AddRec with a GEP. 488453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (const PointerType *PTy = dyn_cast<PointerType>(Base->getType())) { 489f876ad0a70c5c3bb402de2766237410f041700e6Dan Gohman // Make sure the Base isn't something exotic, such as a multiplied 490f876ad0a70c5c3bb402de2766237410f041700e6Dan Gohman // or divided pointer value. In those cases, the result type isn't 491f876ad0a70c5c3bb402de2766237410f041700e6Dan Gohman // actually a pointer type. 492f876ad0a70c5c3bb402de2766237410f041700e6Dan Gohman if (!isa<SCEVMulExpr>(Base) && !isa<SCEVUDivExpr>(Base)) { 493f876ad0a70c5c3bb402de2766237410f041700e6Dan Gohman Value *StartV = expand(Base); 494f876ad0a70c5c3bb402de2766237410f041700e6Dan Gohman assert(StartV->getType() == PTy && "Pointer type mismatch for GEP!"); 495f876ad0a70c5c3bb402de2766237410f041700e6Dan Gohman return expandAddToGEP(RestArray, RestArray+1, PTy, Ty, StartV); 496f876ad0a70c5c3bb402de2766237410f041700e6Dan Gohman } 497453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 498453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 499453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman 500453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman Value *RestV = expand(Rest); 501453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman return expand(SE.getAddExpr(S->getStart(), SE.getUnknown(RestV))); 50236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman } 50336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 50436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // {0,+,1} --> Insert a canonical induction variable into the loop! 50517f1972c770dc18f5c7c3c95776b4d62ae9e121dDan Gohman if (S->isAffine() && 506246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman S->getOperand(1) == SE.getIntegerSCEV(1, Ty)) { 5074d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // If there's a canonical IV, just use it. 5084d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman if (CanonicalIV) { 5094d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman assert(Ty == SE.getEffectiveSCEVType(CanonicalIV->getType()) && 5104d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman "IVs with types different from the canonical IV should " 5114d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman "already have been handled!"); 5124d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman return CanonicalIV; 5134d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman } 5144d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 51536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // Create and insert the PHI node for the induction variable in the 51636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // specified loop. 51736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman BasicBlock *Header = L->getHeader(); 518051a950000e21935165db56695e35bade668193bGabor Greif PHINode *PN = PHINode::Create(Ty, "indvar", Header->begin()); 519cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(PN); 52036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman PN->addIncoming(Constant::getNullValue(Ty), L->getLoopPreheader()); 52136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 52236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman pred_iterator HPI = pred_begin(Header); 52336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman assert(HPI != pred_end(Header) && "Loop with zero preds???"); 52436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman if (!L->contains(*HPI)) ++HPI; 52536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman assert(HPI != pred_end(Header) && L->contains(*HPI) && 52636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman "No backedge in loop?"); 52736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 52836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // Insert a unit add instruction right before the terminator corresponding 52936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // to the back-edge. 53024d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer Constant *One = ConstantInt::get(Ty, 1); 5317cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Instruction *Add = BinaryOperator::CreateAdd(PN, One, "indvar.next", 53236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman (*HPI)->getTerminator()); 533cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(Add); 53436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 53536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman pred_iterator PI = pred_begin(Header); 53636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman if (*PI == L->getLoopPreheader()) 53736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman ++PI; 53836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman PN->addIncoming(Add, *PI); 53936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman return PN; 54036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman } 54136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 5424d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // {0,+,F} --> {0,+,1} * F 54336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // Get the canonical induction variable I for this loop. 5444d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman Value *I = CanonicalIV ? 5454d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman CanonicalIV : 5464d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman getOrInsertCanonicalInductionVariable(L, Ty); 54736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 548df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // If this is a simple linear addrec, emit it now as a special case. 54917f1972c770dc18f5c7c3c95776b4d62ae9e121dDan Gohman if (S->isAffine()) { // {0,+,F} --> i*F 55092fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *F = expandCodeFor(S->getOperand(1), Ty); 5514d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 552df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // If the insert point is directly inside of the loop, emit the multiply at 553df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // the insert point. Otherwise, L is a loop that is a parent of the insert 554df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // point loop. If we can, move the multiply to the outer most loop that it 555df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // is safe to be in. 5566cdc727f2d7f68734526ef078f4632798ad40791Dan Gohman BasicBlock::iterator MulInsertPt = getInsertionPoint(); 5575be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Loop *InsertPtLoop = SE.LI->getLoopFor(MulInsertPt->getParent()); 558df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner if (InsertPtLoop != L && InsertPtLoop && 559df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner L->contains(InsertPtLoop->getHeader())) { 5605d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz do { 561df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // If we cannot hoist the multiply out of this loop, don't. 562df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner if (!InsertPtLoop->isLoopInvariant(F)) break; 563df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner 5645d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz BasicBlock *InsertPtLoopPH = InsertPtLoop->getLoopPreheader(); 5655d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz 5665d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz // If this loop hasn't got a preheader, we aren't able to hoist the 5675d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz // multiply. 5685d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz if (!InsertPtLoopPH) 5695d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz break; 5705d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz 5715d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz // Otherwise, move the insert point to the preheader. 5725d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz MulInsertPt = InsertPtLoopPH->getTerminator(); 573df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner InsertPtLoop = InsertPtLoop->getParentLoop(); 5745d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz } while (InsertPtLoop != L); 575df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner } 576df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner 5777fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner return InsertBinop(Instruction::Mul, I, F, MulInsertPt); 57836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman } 57936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 58036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // If this is a chain of recurrences, turn it into a closed form, using the 58136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // folders, then expandCodeFor the closed form. This allows the folders to 58236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // simplify the expression without having to build a bunch of special code 58336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // into this folder. 584246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle IH = SE.getUnknown(I); // Get I as a "symbolic" SCEV. 58536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 5864d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // Promote S up to the canonical IV type, if the cast is foldable. 5874d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman SCEVHandle NewS = S; 5884d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman SCEVHandle Ext = SE.getNoopOrAnyExtend(S, I->getType()); 5894d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman if (isa<SCEVAddRecExpr>(Ext)) 5904d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman NewS = Ext; 5914d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 5924d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman SCEVHandle V = cast<SCEVAddRecExpr>(NewS)->evaluateAtIteration(IH, SE); 593e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling //cerr << "Evaluated: " << *this << "\n to: " << *V << "\n"; 59436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 5954d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // Truncate the result down to the original type, if needed. 5964d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman SCEVHandle T = SE.getTruncateOrNoop(V, Ty); 597d19534add90a2a894af61523b830887097bb780bDan Gohman return expand(V); 59836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman} 59996fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov 600890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitTruncateExpr(const SCEVTruncateExpr *S) { 601af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 60292fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *V = expandCodeFor(S->getOperand(), 60392fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman SE.getEffectiveSCEVType(S->getOperand()->getType())); 604cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *I = new TruncInst(V, Ty, "tmp.", InsertPt); 605cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(I); 606cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman return I; 60711f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman} 60811f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman 609890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitZeroExtendExpr(const SCEVZeroExtendExpr *S) { 610af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 61192fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *V = expandCodeFor(S->getOperand(), 61292fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman SE.getEffectiveSCEVType(S->getOperand()->getType())); 613cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *I = new ZExtInst(V, Ty, "tmp.", InsertPt); 614cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(I); 615cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman return I; 61611f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman} 61711f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman 618890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitSignExtendExpr(const SCEVSignExtendExpr *S) { 619af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 62092fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *V = expandCodeFor(S->getOperand(), 62192fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman SE.getEffectiveSCEVType(S->getOperand()->getType())); 622cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *I = new SExtInst(V, Ty, "tmp.", InsertPt); 623cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(I); 624cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman return I; 62511f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman} 62611f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman 627890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitSMaxExpr(const SCEVSMaxExpr *S) { 628af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 62992fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *LHS = expandCodeFor(S->getOperand(0), Ty); 630c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky for (unsigned i = 1; i < S->getNumOperands(); ++i) { 63192fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *RHS = expandCodeFor(S->getOperand(i), Ty); 632cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *ICmp = 633cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman new ICmpInst(ICmpInst::ICMP_SGT, LHS, RHS, "tmp", InsertPt); 634cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(ICmp); 635cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *Sel = SelectInst::Create(ICmp, LHS, RHS, "smax", InsertPt); 636cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(Sel); 637cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman LHS = Sel; 638c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky } 639c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky return LHS; 640c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky} 641c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky 642890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitUMaxExpr(const SCEVUMaxExpr *S) { 643af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 64492fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *LHS = expandCodeFor(S->getOperand(0), Ty); 6453e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky for (unsigned i = 1; i < S->getNumOperands(); ++i) { 64692fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *RHS = expandCodeFor(S->getOperand(i), Ty); 647cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *ICmp = 648cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman new ICmpInst(ICmpInst::ICMP_UGT, LHS, RHS, "tmp", InsertPt); 649cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(ICmp); 650cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *Sel = SelectInst::Create(ICmp, LHS, RHS, "umax", InsertPt); 651cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(Sel); 652cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman LHS = Sel; 6533e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky } 6543e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky return LHS; 6553e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky} 6563e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky 657752ec7da506f5d41c08bd37e195750b57550ce68Dan GohmanValue *SCEVExpander::expandCodeFor(SCEVHandle SH, const Type *Ty) { 65811f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman // Expand the code for this SCEV. 6592d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman Value *V = expand(SH); 6605be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (Ty) { 6615be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman assert(SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType()) && 6625be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman "non-trivial casts should be done with the SCEVs directly!"); 6635be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman V = InsertNoopCastOfTo(V, Ty); 6645be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 6655be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman return V; 66611f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman} 66711f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman 668890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::expand(const SCEV *S) { 66996fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov // Check to see if we already expanded this. 6703790fb0c036acaa4db50aff83dd8b3bf51f8af6aTorok Edwin std::map<SCEVHandle, AssertingVH<Value> >::iterator I = 6713790fb0c036acaa4db50aff83dd8b3bf51f8af6aTorok Edwin InsertedExpressions.find(S); 67296fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov if (I != InsertedExpressions.end()) 67396fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov return I->second; 67496fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov 67596fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov Value *V = visit(S); 67696fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov InsertedExpressions[S] = V; 67796fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov return V; 67896fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov} 6791d09de3eca23267855e28297fcb40de3632ea47bDan Gohman 6801d09de3eca23267855e28297fcb40de3632ea47bDan Gohman/// getOrInsertCanonicalInductionVariable - This method returns the 6811d09de3eca23267855e28297fcb40de3632ea47bDan Gohman/// canonical induction variable of the specified type for the specified 6821d09de3eca23267855e28297fcb40de3632ea47bDan Gohman/// loop (inserting one if there is none). A canonical induction variable 6831d09de3eca23267855e28297fcb40de3632ea47bDan Gohman/// starts at zero and steps by one on each iteration. 6841d09de3eca23267855e28297fcb40de3632ea47bDan GohmanValue * 6851d09de3eca23267855e28297fcb40de3632ea47bDan GohmanSCEVExpander::getOrInsertCanonicalInductionVariable(const Loop *L, 6861d09de3eca23267855e28297fcb40de3632ea47bDan Gohman const Type *Ty) { 6871d09de3eca23267855e28297fcb40de3632ea47bDan Gohman assert(Ty->isInteger() && "Can only insert integer induction variables!"); 6881d09de3eca23267855e28297fcb40de3632ea47bDan Gohman SCEVHandle H = SE.getAddRecExpr(SE.getIntegerSCEV(0, Ty), 6891d09de3eca23267855e28297fcb40de3632ea47bDan Gohman SE.getIntegerSCEV(1, Ty), L); 6901d09de3eca23267855e28297fcb40de3632ea47bDan Gohman return expand(H); 6911d09de3eca23267855e28297fcb40de3632ea47bDan Gohman} 692