ScalarEvolutionExpander.cpp revision 1d0be15f89cb5056e20e2d24faa8d6afb1573bca
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" 1876f600b205606a055ec35e7d3fd1a99602329d67Owen Anderson#include "llvm/LLVMContext.h" 195be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman#include "llvm/Target/TargetData.h" 204d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman#include "llvm/ADT/STLExtras.h" 2136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begemanusing namespace llvm; 2236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 23267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman/// InsertNoopCastOfTo - Insert a cast of V to the specified type, 24267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman/// which must be possible with a noop cast, doing what we can to share 25267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman/// the casts. 26267a385342f2e7388f178b327dd87c5f29afd51bDan GohmanValue *SCEVExpander::InsertNoopCastOfTo(Value *V, const Type *Ty) { 27267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman Instruction::CastOps Op = CastInst::getCastOpcode(V, false, Ty, false); 28267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman assert((Op == Instruction::BitCast || 29267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman Op == Instruction::PtrToInt || 30267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman Op == Instruction::IntToPtr) && 31267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman "InsertNoopCastOfTo cannot perform non-noop casts!"); 32267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman assert(SE.getTypeSizeInBits(V->getType()) == SE.getTypeSizeInBits(Ty) && 33267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman "InsertNoopCastOfTo cannot change sizes!"); 34267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman 352d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman // Short-circuit unnecessary bitcasts. 36267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman if (Op == Instruction::BitCast && V->getType() == Ty) 372d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman return V; 382d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman 39f04fa483b83227c570bc58e1684ea096430a6697Dan Gohman // Short-circuit unnecessary inttoptr<->ptrtoint casts. 40267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman if ((Op == Instruction::PtrToInt || Op == Instruction::IntToPtr) && 4180dcdee0f48820ecea86c15768324945bb0d68d1Dan Gohman SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(V->getType())) { 42af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman if (CastInst *CI = dyn_cast<CastInst>(V)) 43af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman if ((CI->getOpcode() == Instruction::PtrToInt || 44af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman CI->getOpcode() == Instruction::IntToPtr) && 45af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman SE.getTypeSizeInBits(CI->getType()) == 46af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman SE.getTypeSizeInBits(CI->getOperand(0)->getType())) 47af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman return CI->getOperand(0); 4880dcdee0f48820ecea86c15768324945bb0d68d1Dan Gohman if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 4980dcdee0f48820ecea86c15768324945bb0d68d1Dan Gohman if ((CE->getOpcode() == Instruction::PtrToInt || 5080dcdee0f48820ecea86c15768324945bb0d68d1Dan Gohman CE->getOpcode() == Instruction::IntToPtr) && 5180dcdee0f48820ecea86c15768324945bb0d68d1Dan Gohman SE.getTypeSizeInBits(CE->getType()) == 5280dcdee0f48820ecea86c15768324945bb0d68d1Dan Gohman SE.getTypeSizeInBits(CE->getOperand(0)->getType())) 5380dcdee0f48820ecea86c15768324945bb0d68d1Dan Gohman return CE->getOperand(0); 5480dcdee0f48820ecea86c15768324945bb0d68d1Dan Gohman } 55f04fa483b83227c570bc58e1684ea096430a6697Dan Gohman 56ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner // FIXME: keep track of the cast instruction. 57ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if (Constant *C = dyn_cast<Constant>(V)) 58baf3c404409d5e47b13984a7f95bfbd6d1f2e79eOwen Anderson return ConstantExpr::getCast(Op, C, Ty); 59ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner 60ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if (Argument *A = dyn_cast<Argument>(V)) { 61ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner // Check to see if there is already a cast! 62ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner for (Value::use_iterator UI = A->use_begin(), E = A->use_end(); 6340a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman UI != E; ++UI) 64ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if ((*UI)->getType() == Ty) 653913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (CastInst *CI = dyn_cast<CastInst>(cast<Instruction>(*UI))) 66267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman if (CI->getOpcode() == Op) { 673913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz // If the cast isn't the first instruction of the function, move it. 6840a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman if (BasicBlock::iterator(CI) != 693913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz A->getParent()->getEntryBlock().begin()) { 7040a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman // Recreate the cast at the beginning of the entry block. 7140a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman // The old cast is left in place in case it is being used 7240a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman // as an insert point. 7340a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman Instruction *NewCI = 74267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman CastInst::Create(Op, V, Ty, "", 7540a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman A->getParent()->getEntryBlock().begin()); 7640a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman NewCI->takeName(CI); 7740a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman CI->replaceAllUsesWith(NewCI); 7840a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman return NewCI; 793913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz } 803913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz return CI; 81ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 8240a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman 83267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman Instruction *I = CastInst::Create(Op, V, Ty, V->getName(), 84cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman A->getParent()->getEntryBlock().begin()); 85cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(I); 86cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman return I; 87ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 883913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz 89ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner Instruction *I = cast<Instruction>(V); 903913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz 91ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner // Check to see if there is already a cast. If there is, use it. 92ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 93ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner UI != E; ++UI) { 94ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if ((*UI)->getType() == Ty) 953913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (CastInst *CI = dyn_cast<CastInst>(cast<Instruction>(*UI))) 96267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman if (CI->getOpcode() == Op) { 973913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz BasicBlock::iterator It = I; ++It; 983913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (isa<InvokeInst>(I)) 993913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz It = cast<InvokeInst>(I)->getNormalDest()->begin(); 1003913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz while (isa<PHINode>(It)) ++It; 1013913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (It != BasicBlock::iterator(CI)) { 10240a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman // Recreate the cast at the beginning of the entry block. 10340a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman // The old cast is left in place in case it is being used 10440a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman // as an insert point. 105267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman Instruction *NewCI = CastInst::Create(Op, V, Ty, "", It); 10640a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman NewCI->takeName(CI); 10740a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman CI->replaceAllUsesWith(NewCI); 10840a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman return NewCI; 1093913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz } 1103913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz return CI; 111ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 112ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 113ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner BasicBlock::iterator IP = I; ++IP; 114ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if (InvokeInst *II = dyn_cast<InvokeInst>(I)) 115ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner IP = II->getNormalDest()->begin(); 116ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner while (isa<PHINode>(IP)) ++IP; 117267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman Instruction *CI = CastInst::Create(Op, V, Ty, V->getName(), IP); 118cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(CI); 119cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman return CI; 120ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner} 121ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner 1227fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner/// InsertBinop - Insert the specified binary operator, doing a small amount 1237fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner/// of work to avoid inserting an obviously redundant operation. 124267a385342f2e7388f178b327dd87c5f29afd51bDan GohmanValue *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode, 125267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman Value *LHS, Value *RHS) { 1260f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman // Fold a binop with constant operands. 1270f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman if (Constant *CLHS = dyn_cast<Constant>(LHS)) 1280f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman if (Constant *CRHS = dyn_cast<Constant>(RHS)) 129baf3c404409d5e47b13984a7f95bfbd6d1f2e79eOwen Anderson return ConstantExpr::get(Opcode, CLHS, CRHS); 1300f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman 1317fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner // Do a quick scan to see if we have this binop nearby. If so, reuse it. 1327fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner unsigned ScanLimit = 6; 133267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman BasicBlock::iterator BlockBegin = Builder.GetInsertBlock()->begin(); 134267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman // Scanning starts from the last instruction before the insertion point. 135267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman BasicBlock::iterator IP = Builder.GetInsertPoint(); 136267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman if (IP != BlockBegin) { 1378a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz --IP; 1388a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz for (; ScanLimit; --IP, --ScanLimit) { 1395be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (IP->getOpcode() == (unsigned)Opcode && IP->getOperand(0) == LHS && 1405be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman IP->getOperand(1) == RHS) 1415be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman return IP; 1428a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz if (IP == BlockBegin) break; 1438a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz } 1447fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner } 145267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman 1468a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz // If we haven't found this binop, insert it. 147267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman Value *BO = Builder.CreateBinOp(Opcode, LHS, RHS, "tmp"); 148cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(BO); 149cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman return BO; 1507fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner} 1517fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner 1524a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman/// FactorOutConstant - Test if S is divisible by Factor, using signed 153453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// division. If so, update S with Factor divided out and return true. 1544a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman/// S need not be evenly divisble if a reasonable remainder can be 1554a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman/// computed. 156453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// TODO: When ScalarEvolution gets a SCEVSDivExpr, this can be made 157453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// unnecessary; in its place, just signed-divide Ops[i] by the scale and 158453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// check to see if the divide was folded. 1590bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohmanstatic bool FactorOutConstant(const SCEV *&S, 1600bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *&Remainder, 161453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman const APInt &Factor, 162453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman ScalarEvolution &SE) { 163453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // Everything is divisible by one. 164453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (Factor == 1) 165453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman return true; 166453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman 167453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // For a Constant, check for a multiple of the given factor. 1684a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) { 1694a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman ConstantInt *CI = 170eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson ConstantInt::get(SE.getContext(), C->getValue()->getValue().sdiv(Factor)); 1714a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman // If the quotient is zero and the remainder is non-zero, reject 1724a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman // the value at this scale. It will be considered for subsequent 1734a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman // smaller scales. 1744a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman if (C->isZero() || !CI->isZero()) { 1750bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *Div = SE.getConstant(CI); 176453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman S = Div; 1774a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman Remainder = 1784a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman SE.getAddExpr(Remainder, 1794a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman SE.getConstant(C->getValue()->getValue().srem(Factor))); 180453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman return true; 181453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 1824a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman } 183453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman 184453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // In a Mul, check if there is a constant operand which is a multiple 185453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // of the given factor. 186453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) 187453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (const SCEVConstant *C = dyn_cast<SCEVConstant>(M->getOperand(0))) 188453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (!C->getValue()->getValue().srem(Factor)) { 1895001c21712f2e52fd6254461b2b2edb9a5823d23Dan Gohman const SmallVectorImpl<const SCEV *> &MOperands = M->getOperands(); 1905001c21712f2e52fd6254461b2b2edb9a5823d23Dan Gohman SmallVector<const SCEV *, 4> NewMulOps(MOperands.begin(), 1915001c21712f2e52fd6254461b2b2edb9a5823d23Dan Gohman MOperands.end()); 192453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman NewMulOps[0] = 193453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman SE.getConstant(C->getValue()->getValue().sdiv(Factor)); 194453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman S = SE.getMulExpr(NewMulOps); 195453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman return true; 196453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 197453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman 198453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // In an AddRec, check if both start and step are divisible. 199453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) { 2000bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *Step = A->getStepRecurrence(SE); 2010bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *StepRem = SE.getIntegerSCEV(0, Step->getType()); 2024a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman if (!FactorOutConstant(Step, StepRem, Factor, SE)) 2034a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman return false; 2044a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman if (!StepRem->isZero()) 2054a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman return false; 2060bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *Start = A->getStart(); 2074a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman if (!FactorOutConstant(Start, Remainder, Factor, SE)) 208453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman return false; 209453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman S = SE.getAddRecExpr(Start, Step, A->getLoop()); 210453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman return true; 211453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 212453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman 213453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman return false; 214453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman} 215453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman 2165be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman/// expandAddToGEP - Expand a SCEVAddExpr with a pointer type into a GEP 217453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// instead of using ptrtoint+arithmetic+inttoptr. This helps 21813c5e35222afe0895f0c5e68aa9f22f134ea437aDan Gohman/// BasicAliasAnalysis analyze the result. 21913c5e35222afe0895f0c5e68aa9f22f134ea437aDan Gohman/// 22013c5e35222afe0895f0c5e68aa9f22f134ea437aDan Gohman/// Design note: This depends on ScalarEvolution not recognizing inttoptr 22113c5e35222afe0895f0c5e68aa9f22f134ea437aDan Gohman/// and ptrtoint operators, as they may introduce pointer arithmetic 22213c5e35222afe0895f0c5e68aa9f22f134ea437aDan Gohman/// which may not be safely converted into getelementptr. 223453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// 224453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// Design note: It might seem desirable for this function to be more 225453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// loop-aware. If some of the indices are loop-invariant while others 226453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// aren't, it might seem desirable to emit multiple GEPs, keeping the 227453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// loop-invariant portions of the overall computation outside the loop. 228453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// However, there are a few reasons this is not done here. Hoisting simple 229453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// arithmetic is a low-level optimization that often isn't very 230453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// important until late in the optimization process. In fact, passes 231453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// like InstructionCombining will combine GEPs, even if it means 232453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// pushing loop-invariant computation down into loops, so even if the 233453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// GEPs were split here, the work would quickly be undone. The 234453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// LoopStrengthReduction pass, which is usually run quite late (and 235453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// after the last InstructionCombining pass), takes care of hoisting 236453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// loop-invariant portions of expressions, after considering what 237453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// can be folded using target addressing modes. 238453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// 2390bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan GohmanValue *SCEVExpander::expandAddToGEP(const SCEV *const *op_begin, 2400bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *const *op_end, 2415be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman const PointerType *PTy, 2425be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman const Type *Ty, 2435be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Value *V) { 2445be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman const Type *ElTy = PTy->getElementType(); 2455be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman SmallVector<Value *, 4> GepIndices; 2460bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman SmallVector<const SCEV *, 8> Ops(op_begin, op_end); 2475be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman bool AnyNonZeroIndices = false; 2485be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 2495be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // Decend down the pointer's type and attempt to convert the other 2505be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // operands into GEP indices, at each level. The first index in a GEP 2515be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // indexes into the array implied by the pointer operand; the rest of 2525be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // the indices index into the element or field type selected by the 2535be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // preceding index. 2545be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman for (;;) { 2555be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman APInt ElSize = APInt(SE.getTypeSizeInBits(Ty), 2565be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman ElTy->isSized() ? SE.TD->getTypeAllocSize(ElTy) : 0); 2570bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman SmallVector<const SCEV *, 8> NewOps; 2580bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman SmallVector<const SCEV *, 8> ScaledOps; 2595be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 260453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // Split AddRecs up into parts as either of the parts may be usable 261453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // without the other. 262453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Ops[i])) 263453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (!A->getStart()->isZero()) { 2640bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *Start = A->getStart(); 265453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman Ops.push_back(SE.getAddRecExpr(SE.getIntegerSCEV(0, A->getType()), 266453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman A->getStepRecurrence(SE), 267453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman A->getLoop())); 268453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman Ops[i] = Start; 269453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman ++e; 270453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 271453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // If the scale size is not 0, attempt to factor out a scale. 2725be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (ElSize != 0) { 2730bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *Op = Ops[i]; 2740bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *Remainder = SE.getIntegerSCEV(0, Op->getType()); 2754a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman if (FactorOutConstant(Op, Remainder, ElSize, SE)) { 276453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman ScaledOps.push_back(Op); // Op now has ElSize factored out. 2774a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman NewOps.push_back(Remainder); 2785be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman continue; 2795be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 2805be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 281453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // If the operand was not divisible, add it to the list of operands 282453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // we'll scan next iteration. 2835be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman NewOps.push_back(Ops[i]); 2845be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 2855be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Ops = NewOps; 2865be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman AnyNonZeroIndices |= !ScaledOps.empty(); 2875be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Value *Scaled = ScaledOps.empty() ? 288a7235ea7245028a0723e8ab7fd011386b3900777Owen Anderson Constant::getNullValue(Ty) : 2895be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman expandCodeFor(SE.getAddExpr(ScaledOps), Ty); 2905be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman GepIndices.push_back(Scaled); 2915be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 2925be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // Collect struct field index operands. 2935be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (!Ops.empty()) 2945be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman while (const StructType *STy = dyn_cast<StructType>(ElTy)) { 2955be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[0])) 2965be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (SE.getTypeSizeInBits(C->getType()) <= 64) { 2975be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman const StructLayout &SL = *SE.TD->getStructLayout(STy); 2985be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman uint64_t FullOffset = C->getValue()->getZExtValue(); 2995be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (FullOffset < SL.getSizeInBytes()) { 3005be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman unsigned ElIdx = SL.getElementContainingOffset(FullOffset); 3011d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson GepIndices.push_back( 3021d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson ConstantInt::get(Type::getInt32Ty(Ty->getContext()), ElIdx)); 3035be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman ElTy = STy->getTypeAtIndex(ElIdx); 3045be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Ops[0] = 3056de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman SE.getConstant(Ty, FullOffset - SL.getElementOffset(ElIdx)); 3065be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman AnyNonZeroIndices = true; 3075be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman continue; 3085be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 3095be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 3105be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman break; 3115be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 3125be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 3135be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (const ArrayType *ATy = dyn_cast<ArrayType>(ElTy)) { 3145be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman ElTy = ATy->getElementType(); 3155be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman continue; 3165be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 3175be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman break; 3185be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 3195be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 3205be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // If none of the operands were convertable to proper GEP indices, cast 3215be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // the base to i8* and do an ugly getelementptr with that. It's still 3225be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // better than ptrtoint+arithmetic+inttoptr at least. 3235be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (!AnyNonZeroIndices) { 3245be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman V = InsertNoopCastOfTo(V, 3251d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Type::getInt8Ty(Ty->getContext())->getPointerTo(PTy->getAddressSpace())); 32692fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *Idx = expandCodeFor(SE.getAddExpr(Ops), Ty); 3275be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 3285be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // Fold a GEP with constant operands. 3295be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (Constant *CLHS = dyn_cast<Constant>(V)) 3305be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (Constant *CRHS = dyn_cast<Constant>(Idx)) 331baf3c404409d5e47b13984a7f95bfbd6d1f2e79eOwen Anderson return ConstantExpr::getGetElementPtr(CLHS, &CRHS, 1); 3325be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 3335be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // Do a quick scan to see if we have this GEP nearby. If so, reuse it. 3345be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman unsigned ScanLimit = 6; 335267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman BasicBlock::iterator BlockBegin = Builder.GetInsertBlock()->begin(); 336267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman // Scanning starts from the last instruction before the insertion point. 337267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman BasicBlock::iterator IP = Builder.GetInsertPoint(); 338267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman if (IP != BlockBegin) { 3395be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman --IP; 3405be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman for (; ScanLimit; --IP, --ScanLimit) { 3415be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (IP->getOpcode() == Instruction::GetElementPtr && 3425be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman IP->getOperand(0) == V && IP->getOperand(1) == Idx) 3435be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman return IP; 3445be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (IP == BlockBegin) break; 3455be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 3465be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 3475be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 348267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman Value *GEP = Builder.CreateGEP(V, Idx, "scevgep"); 3495be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman InsertedValues.insert(GEP); 3505be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman return GEP; 3515be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 3525be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 353d6aa02de1076c801ac41295156a2379637976918Dan Gohman // Insert a pretty getelementptr. Note that this GEP is not marked inbounds, 354d6aa02de1076c801ac41295156a2379637976918Dan Gohman // because ScalarEvolution may have changed the address arithmetic to 355d6aa02de1076c801ac41295156a2379637976918Dan Gohman // compute a value which is beyond the end of the allocated object. 356267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman Value *GEP = Builder.CreateGEP(V, 357267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman GepIndices.begin(), 358267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman GepIndices.end(), 359267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman "scevgep"); 3605be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Ops.push_back(SE.getUnknown(GEP)); 3615be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman InsertedValues.insert(GEP); 3625be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman return expand(SE.getAddExpr(Ops)); 3635be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman} 3645be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 365890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitAddExpr(const SCEVAddExpr *S) { 366af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 367e24fa64d52330626553298f56ba5aa702624c282Dan Gohman Value *V = expand(S->getOperand(S->getNumOperands()-1)); 3685be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 369453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // Turn things like ptrtoint+arithmetic+inttoptr into GEP. See the 370453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // comments on expandAddToGEP for details. 3715be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (SE.TD) 372453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (const PointerType *PTy = dyn_cast<PointerType>(V->getType())) { 3730bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SmallVectorImpl<const SCEV *> &Ops = S->getOperands(); 3745001c21712f2e52fd6254461b2b2edb9a5823d23Dan Gohman return expandAddToGEP(&Ops[0], &Ops[Ops.size() - 1], PTy, Ty, V); 375453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 3765be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 377af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman V = InsertNoopCastOfTo(V, Ty); 378e24fa64d52330626553298f56ba5aa702624c282Dan Gohman 379e24fa64d52330626553298f56ba5aa702624c282Dan Gohman // Emit a bunch of add instructions 3802d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman for (int i = S->getNumOperands()-2; i >= 0; --i) { 38192fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *W = expandCodeFor(S->getOperand(i), Ty); 382267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman V = InsertBinop(Instruction::Add, V, W); 3832d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman } 384e24fa64d52330626553298f56ba5aa702624c282Dan Gohman return V; 385e24fa64d52330626553298f56ba5aa702624c282Dan Gohman} 3865be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 387890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) { 388af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 38936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman int FirstOp = 0; // Set if we should emit a subtract. 390890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getOperand(0))) 39136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman if (SC->getValue()->isAllOnesValue()) 39236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman FirstOp = 1; 39336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 39436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman int i = S->getNumOperands()-2; 39592fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *V = expandCodeFor(S->getOperand(i+1), Ty); 39636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 39736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // Emit a bunch of multiply instructions 3982d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman for (; i >= FirstOp; --i) { 39992fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *W = expandCodeFor(S->getOperand(i), Ty); 400267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman V = InsertBinop(Instruction::Mul, V, W); 4012d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman } 4022d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman 40336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // -1 * ... ---> 0 - ... 40436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman if (FirstOp == 1) 405a7235ea7245028a0723e8ab7fd011386b3900777Owen Anderson V = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), V); 40636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman return V; 40736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman} 40836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 409890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitUDivExpr(const SCEVUDivExpr *S) { 410af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 4112d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman 41292fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *LHS = expandCodeFor(S->getLHS(), Ty); 413890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getRHS())) { 4146177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky const APInt &RHS = SC->getValue()->getValue(); 4156177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky if (RHS.isPowerOf2()) 4166177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky return InsertBinop(Instruction::LShr, LHS, 417eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson ConstantInt::get(Ty, RHS.logBase2())); 4186177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky } 4196177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky 42092fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *RHS = expandCodeFor(S->getRHS(), Ty); 421267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman return InsertBinop(Instruction::UDiv, LHS, RHS); 4226177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky} 4236177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky 424453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// Move parts of Base into Rest to leave Base with the minimal 425453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// expression that provides a pointer operand suitable for a 426453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// GEP expansion. 4270bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohmanstatic void ExposePointerBase(const SCEV *&Base, const SCEV *&Rest, 428453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman ScalarEvolution &SE) { 429453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman while (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Base)) { 430453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman Base = A->getStart(); 431453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman Rest = SE.getAddExpr(Rest, 432453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman SE.getAddRecExpr(SE.getIntegerSCEV(0, A->getType()), 433453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman A->getStepRecurrence(SE), 434453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman A->getLoop())); 435453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 436453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(Base)) { 437453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman Base = A->getOperand(A->getNumOperands()-1); 4380bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman SmallVector<const SCEV *, 8> NewAddOps(A->op_begin(), A->op_end()); 439453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman NewAddOps.back() = Rest; 440453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman Rest = SE.getAddExpr(NewAddOps); 441453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman ExposePointerBase(Base, Rest, SE); 442453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 443453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman} 444453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman 445890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) { 446af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 44736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman const Loop *L = S->getLoop(); 44836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 4494d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // First check for an existing canonical IV in a suitable type. 4504d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman PHINode *CanonicalIV = 0; 4514d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman if (PHINode *PN = L->getCanonicalInductionVariable()) 4524d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman if (SE.isSCEVable(PN->getType()) && 4534d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman isa<IntegerType>(SE.getEffectiveSCEVType(PN->getType())) && 4544d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman SE.getTypeSizeInBits(PN->getType()) >= SE.getTypeSizeInBits(Ty)) 4554d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman CanonicalIV = PN; 4564d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 4574d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // Rewrite an AddRec in terms of the canonical induction variable, if 4584d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // its type is more narrow. 4594d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman if (CanonicalIV && 4604d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman SE.getTypeSizeInBits(CanonicalIV->getType()) > 4614d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman SE.getTypeSizeInBits(Ty)) { 4625001c21712f2e52fd6254461b2b2edb9a5823d23Dan Gohman const SCEV *Start = SE.getAnyExtendExpr(S->getStart(), 4635001c21712f2e52fd6254461b2b2edb9a5823d23Dan Gohman CanonicalIV->getType()); 4645001c21712f2e52fd6254461b2b2edb9a5823d23Dan Gohman const SCEV *Step = SE.getAnyExtendExpr(S->getStepRecurrence(SE), 4654d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman CanonicalIV->getType()); 4664d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman Value *V = expand(SE.getAddRecExpr(Start, Step, S->getLoop())); 467267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman BasicBlock *SaveInsertBB = Builder.GetInsertBlock(); 468267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint(); 4694d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman BasicBlock::iterator NewInsertPt = 4704d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman next(BasicBlock::iterator(cast<Instruction>(V))); 4714d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman while (isa<PHINode>(NewInsertPt)) ++NewInsertPt; 4724d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman V = expandCodeFor(SE.getTruncateExpr(SE.getUnknown(V), Ty), 0, 4734d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman NewInsertPt); 474267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman Builder.SetInsertPoint(SaveInsertBB, SaveInsertPt); 4754d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman return V; 4764d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman } 4774d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 47836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // {X,+,F} --> X + {0,+,F} 479cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman if (!S->getStart()->isZero()) { 4800bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SmallVectorImpl<const SCEV *> &SOperands = S->getOperands(); 4810bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman SmallVector<const SCEV *, 4> NewOps(SOperands.begin(), SOperands.end()); 482246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman NewOps[0] = SE.getIntegerSCEV(0, Ty); 4830bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *Rest = SE.getAddRecExpr(NewOps, L); 484453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman 485453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // Turn things like ptrtoint+arithmetic+inttoptr into GEP. See the 486453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // comments on expandAddToGEP for details. 487453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (SE.TD) { 4880bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *Base = S->getStart(); 4890bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *RestArray[1] = { Rest }; 490453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // Dig into the expression to find the pointer base for a GEP. 491453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman ExposePointerBase(Base, RestArray[0], SE); 492453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // If we found a pointer, expand the AddRec with a GEP. 493453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (const PointerType *PTy = dyn_cast<PointerType>(Base->getType())) { 494f876ad0a70c5c3bb402de2766237410f041700e6Dan Gohman // Make sure the Base isn't something exotic, such as a multiplied 495f876ad0a70c5c3bb402de2766237410f041700e6Dan Gohman // or divided pointer value. In those cases, the result type isn't 496f876ad0a70c5c3bb402de2766237410f041700e6Dan Gohman // actually a pointer type. 497f876ad0a70c5c3bb402de2766237410f041700e6Dan Gohman if (!isa<SCEVMulExpr>(Base) && !isa<SCEVUDivExpr>(Base)) { 498f876ad0a70c5c3bb402de2766237410f041700e6Dan Gohman Value *StartV = expand(Base); 499f876ad0a70c5c3bb402de2766237410f041700e6Dan Gohman assert(StartV->getType() == PTy && "Pointer type mismatch for GEP!"); 500f876ad0a70c5c3bb402de2766237410f041700e6Dan Gohman return expandAddToGEP(RestArray, RestArray+1, PTy, Ty, StartV); 501f876ad0a70c5c3bb402de2766237410f041700e6Dan Gohman } 502453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 503453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 504453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman 50540a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman // Just do a normal add. Pre-expand the operands to suppress folding. 50640a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman return expand(SE.getAddExpr(SE.getUnknown(expand(S->getStart())), 50740a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman SE.getUnknown(expand(Rest)))); 50836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman } 50936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 51036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // {0,+,1} --> Insert a canonical induction variable into the loop! 51117f1972c770dc18f5c7c3c95776b4d62ae9e121dDan Gohman if (S->isAffine() && 512246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman S->getOperand(1) == SE.getIntegerSCEV(1, Ty)) { 5134d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // If there's a canonical IV, just use it. 5144d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman if (CanonicalIV) { 5154d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman assert(Ty == SE.getEffectiveSCEVType(CanonicalIV->getType()) && 5164d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman "IVs with types different from the canonical IV should " 5174d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman "already have been handled!"); 5184d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman return CanonicalIV; 5194d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman } 5204d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 52136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // Create and insert the PHI node for the induction variable in the 52236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // specified loop. 52336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman BasicBlock *Header = L->getHeader(); 524267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman BasicBlock *Preheader = L->getLoopPreheader(); 525051a950000e21935165db56695e35bade668193bGabor Greif PHINode *PN = PHINode::Create(Ty, "indvar", Header->begin()); 526cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(PN); 527a7235ea7245028a0723e8ab7fd011386b3900777Owen Anderson PN->addIncoming(Constant::getNullValue(Ty), Preheader); 52836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 52936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman pred_iterator HPI = pred_begin(Header); 53036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman assert(HPI != pred_end(Header) && "Loop with zero preds???"); 53136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman if (!L->contains(*HPI)) ++HPI; 53236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman assert(HPI != pred_end(Header) && L->contains(*HPI) && 53336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman "No backedge in loop?"); 53436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 53536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // Insert a unit add instruction right before the terminator corresponding 53636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // to the back-edge. 537eed707b1e6097aac2bb6b3d47271f6300ace7f2eOwen Anderson Constant *One = ConstantInt::get(Ty, 1); 5387cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Instruction *Add = BinaryOperator::CreateAdd(PN, One, "indvar.next", 53936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman (*HPI)->getTerminator()); 540cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(Add); 54136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 54236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman pred_iterator PI = pred_begin(Header); 543267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman if (*PI == Preheader) 54436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman ++PI; 54536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman PN->addIncoming(Add, *PI); 54636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman return PN; 54736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman } 54836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 5494d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // {0,+,F} --> {0,+,1} * F 55036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // Get the canonical induction variable I for this loop. 5514d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman Value *I = CanonicalIV ? 5524d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman CanonicalIV : 5534d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman getOrInsertCanonicalInductionVariable(L, Ty); 55436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 555df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // If this is a simple linear addrec, emit it now as a special case. 55640a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman if (S->isAffine()) // {0,+,F} --> i*F 55740a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman return 55840a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman expand(SE.getTruncateOrNoop( 55940a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman SE.getMulExpr(SE.getUnknown(I), 56040a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman SE.getNoopOrAnyExtend(S->getOperand(1), 56140a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman I->getType())), 56240a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman Ty)); 56336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 56436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // If this is a chain of recurrences, turn it into a closed form, using the 56536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // folders, then expandCodeFor the closed form. This allows the folders to 56636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // simplify the expression without having to build a bunch of special code 56736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // into this folder. 5680bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *IH = SE.getUnknown(I); // Get I as a "symbolic" SCEV. 56936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 5704d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // Promote S up to the canonical IV type, if the cast is foldable. 5710bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *NewS = S; 5720bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *Ext = SE.getNoopOrAnyExtend(S, I->getType()); 5734d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman if (isa<SCEVAddRecExpr>(Ext)) 5744d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman NewS = Ext; 5754d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 5760bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *V = cast<SCEVAddRecExpr>(NewS)->evaluateAtIteration(IH, SE); 577e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling //cerr << "Evaluated: " << *this << "\n to: " << *V << "\n"; 57836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 5794d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // Truncate the result down to the original type, if needed. 5800bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *T = SE.getTruncateOrNoop(V, Ty); 581469f3cdc13851914f3a766cbd8f701cf8431cacaDan Gohman return expand(T); 58236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman} 58396fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov 584890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitTruncateExpr(const SCEVTruncateExpr *S) { 585af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 58692fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *V = expandCodeFor(S->getOperand(), 58792fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman SE.getEffectiveSCEVType(S->getOperand()->getType())); 588267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman Value *I = Builder.CreateTrunc(V, Ty, "tmp"); 589cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(I); 590cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman return I; 59111f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman} 59211f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman 593890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitZeroExtendExpr(const SCEVZeroExtendExpr *S) { 594af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 59592fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *V = expandCodeFor(S->getOperand(), 59692fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman SE.getEffectiveSCEVType(S->getOperand()->getType())); 597267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman Value *I = Builder.CreateZExt(V, Ty, "tmp"); 598cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(I); 599cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman return I; 60011f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman} 60111f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman 602890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitSignExtendExpr(const SCEVSignExtendExpr *S) { 603af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 60492fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *V = expandCodeFor(S->getOperand(), 60592fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman SE.getEffectiveSCEVType(S->getOperand()->getType())); 606267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman Value *I = Builder.CreateSExt(V, Ty, "tmp"); 607cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(I); 608cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman return I; 60911f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman} 61011f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman 611890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitSMaxExpr(const SCEVSMaxExpr *S) { 6120196dc5733bf3c6a71f7de1f631f2c43e5809fd9Dan Gohman Value *LHS = expand(S->getOperand(S->getNumOperands()-1)); 6130196dc5733bf3c6a71f7de1f631f2c43e5809fd9Dan Gohman const Type *Ty = LHS->getType(); 6140196dc5733bf3c6a71f7de1f631f2c43e5809fd9Dan Gohman for (int i = S->getNumOperands()-2; i >= 0; --i) { 6150196dc5733bf3c6a71f7de1f631f2c43e5809fd9Dan Gohman // In the case of mixed integer and pointer types, do the 6160196dc5733bf3c6a71f7de1f631f2c43e5809fd9Dan Gohman // rest of the comparisons as integer. 6170196dc5733bf3c6a71f7de1f631f2c43e5809fd9Dan Gohman if (S->getOperand(i)->getType() != Ty) { 6180196dc5733bf3c6a71f7de1f631f2c43e5809fd9Dan Gohman Ty = SE.getEffectiveSCEVType(Ty); 6190196dc5733bf3c6a71f7de1f631f2c43e5809fd9Dan Gohman LHS = InsertNoopCastOfTo(LHS, Ty); 6200196dc5733bf3c6a71f7de1f631f2c43e5809fd9Dan Gohman } 62192fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *RHS = expandCodeFor(S->getOperand(i), Ty); 622267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman Value *ICmp = Builder.CreateICmpSGT(LHS, RHS, "tmp"); 623cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(ICmp); 624267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "smax"); 625cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(Sel); 626cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman LHS = Sel; 627c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky } 6280196dc5733bf3c6a71f7de1f631f2c43e5809fd9Dan Gohman // In the case of mixed integer and pointer types, cast the 6290196dc5733bf3c6a71f7de1f631f2c43e5809fd9Dan Gohman // final result back to the pointer type. 6300196dc5733bf3c6a71f7de1f631f2c43e5809fd9Dan Gohman if (LHS->getType() != S->getType()) 6310196dc5733bf3c6a71f7de1f631f2c43e5809fd9Dan Gohman LHS = InsertNoopCastOfTo(LHS, S->getType()); 632c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky return LHS; 633c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky} 634c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky 635890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitUMaxExpr(const SCEVUMaxExpr *S) { 6360196dc5733bf3c6a71f7de1f631f2c43e5809fd9Dan Gohman Value *LHS = expand(S->getOperand(S->getNumOperands()-1)); 6370196dc5733bf3c6a71f7de1f631f2c43e5809fd9Dan Gohman const Type *Ty = LHS->getType(); 6380196dc5733bf3c6a71f7de1f631f2c43e5809fd9Dan Gohman for (int i = S->getNumOperands()-2; i >= 0; --i) { 6390196dc5733bf3c6a71f7de1f631f2c43e5809fd9Dan Gohman // In the case of mixed integer and pointer types, do the 6400196dc5733bf3c6a71f7de1f631f2c43e5809fd9Dan Gohman // rest of the comparisons as integer. 6410196dc5733bf3c6a71f7de1f631f2c43e5809fd9Dan Gohman if (S->getOperand(i)->getType() != Ty) { 6420196dc5733bf3c6a71f7de1f631f2c43e5809fd9Dan Gohman Ty = SE.getEffectiveSCEVType(Ty); 6430196dc5733bf3c6a71f7de1f631f2c43e5809fd9Dan Gohman LHS = InsertNoopCastOfTo(LHS, Ty); 6440196dc5733bf3c6a71f7de1f631f2c43e5809fd9Dan Gohman } 64592fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *RHS = expandCodeFor(S->getOperand(i), Ty); 646267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman Value *ICmp = Builder.CreateICmpUGT(LHS, RHS, "tmp"); 647cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(ICmp); 648267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman Value *Sel = Builder.CreateSelect(ICmp, LHS, RHS, "umax"); 649cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(Sel); 650cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman LHS = Sel; 6513e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky } 6520196dc5733bf3c6a71f7de1f631f2c43e5809fd9Dan Gohman // In the case of mixed integer and pointer types, cast the 6530196dc5733bf3c6a71f7de1f631f2c43e5809fd9Dan Gohman // final result back to the pointer type. 6540196dc5733bf3c6a71f7de1f631f2c43e5809fd9Dan Gohman if (LHS->getType() != S->getType()) 6550196dc5733bf3c6a71f7de1f631f2c43e5809fd9Dan Gohman LHS = InsertNoopCastOfTo(LHS, S->getType()); 6563e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky return LHS; 6573e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky} 6583e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky 6590bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan GohmanValue *SCEVExpander::expandCodeFor(const SCEV *SH, const Type *Ty) { 66011f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman // Expand the code for this SCEV. 6612d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman Value *V = expand(SH); 6625be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (Ty) { 6635be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman assert(SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType()) && 6645be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman "non-trivial casts should be done with the SCEVs directly!"); 6655be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman V = InsertNoopCastOfTo(V, Ty); 6665be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 6675be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman return V; 66811f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman} 66911f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman 670890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::expand(const SCEV *S) { 67140a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman // Compute an insertion point for this SCEV object. Hoist the instructions 67240a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman // as far out in the loop nest as possible. 673267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman Instruction *InsertPt = Builder.GetInsertPoint(); 674267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman for (Loop *L = SE.LI->getLoopFor(Builder.GetInsertBlock()); ; 67540a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman L = L->getParentLoop()) 67640a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman if (S->isLoopInvariant(L)) { 67740a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman if (!L) break; 67840a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman if (BasicBlock *Preheader = L->getLoopPreheader()) 67940a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman InsertPt = Preheader->getTerminator(); 68040a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman } else { 68140a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman // If the SCEV is computable at this level, insert it into the header 68240a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman // after the PHIs (and after any other instructions that we've inserted 68340a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman // there) so that it is guaranteed to dominate any user inside the loop. 68440a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman if (L && S->hasComputableLoopEvolution(L)) 68540a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman InsertPt = L->getHeader()->getFirstNonPHI(); 686267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman while (isInsertedInstruction(InsertPt)) 687267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman InsertPt = next(BasicBlock::iterator(InsertPt)); 68840a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman break; 68940a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman } 69040a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman 691667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // Check to see if we already expanded this here. 692667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman std::map<std::pair<const SCEV *, Instruction *>, 693667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman AssertingVH<Value> >::iterator I = 694667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman InsertedExpressions.find(std::make_pair(S, InsertPt)); 695267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman if (I != InsertedExpressions.end()) 696667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman return I->second; 697267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman 698267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman BasicBlock *SaveInsertBB = Builder.GetInsertBlock(); 699267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint(); 700267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman Builder.SetInsertPoint(InsertPt->getParent(), InsertPt); 701667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman 702667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // Expand the expression into instructions. 70396fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov Value *V = visit(S); 70440a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman 705667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman // Remember the expanded value for this SCEV at this location. 706667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman InsertedExpressions[std::make_pair(S, InsertPt)] = V; 707667d787c0a21cf3f5dfcde03ca471162ba35b614Dan Gohman 708267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman Builder.SetInsertPoint(SaveInsertBB, SaveInsertPt); 70996fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov return V; 71096fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov} 7111d09de3eca23267855e28297fcb40de3632ea47bDan Gohman 7121d09de3eca23267855e28297fcb40de3632ea47bDan Gohman/// getOrInsertCanonicalInductionVariable - This method returns the 7131d09de3eca23267855e28297fcb40de3632ea47bDan Gohman/// canonical induction variable of the specified type for the specified 7141d09de3eca23267855e28297fcb40de3632ea47bDan Gohman/// loop (inserting one if there is none). A canonical induction variable 7151d09de3eca23267855e28297fcb40de3632ea47bDan Gohman/// starts at zero and steps by one on each iteration. 7161d09de3eca23267855e28297fcb40de3632ea47bDan GohmanValue * 7171d09de3eca23267855e28297fcb40de3632ea47bDan GohmanSCEVExpander::getOrInsertCanonicalInductionVariable(const Loop *L, 7181d09de3eca23267855e28297fcb40de3632ea47bDan Gohman const Type *Ty) { 7191d09de3eca23267855e28297fcb40de3632ea47bDan Gohman assert(Ty->isInteger() && "Can only insert integer induction variables!"); 7200bba49cebc50c7bd4662a4807bcb3ee7f42cb470Dan Gohman const SCEV *H = SE.getAddRecExpr(SE.getIntegerSCEV(0, Ty), 72140a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman SE.getIntegerSCEV(1, Ty), L); 722267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman BasicBlock *SaveInsertBB = Builder.GetInsertBlock(); 723267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman BasicBlock::iterator SaveInsertPt = Builder.GetInsertPoint(); 72440a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman Value *V = expandCodeFor(H, 0, L->getHeader()->begin()); 725267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman if (SaveInsertBB) 726267a385342f2e7388f178b327dd87c5f29afd51bDan Gohman Builder.SetInsertPoint(SaveInsertBB, SaveInsertPt); 72740a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman return V; 7281d09de3eca23267855e28297fcb40de3632ea47bDan Gohman} 729