ScalarEvolutionExpander.cpp revision 40a5a1b39ee1cd40ff9d04740386b667fb27b340
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(); 5440a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman 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. 5940a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman if (BasicBlock::iterator(CI) != 603913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz A->getParent()->getEntryBlock().begin()) { 6140a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman // Recreate the cast at the beginning of the entry block. 6240a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman // The old cast is left in place in case it is being used 6340a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman // as an insert point. 6440a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman Instruction *NewCI = 6540a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman CastInst::Create(opcode, V, Ty, "", 6640a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman A->getParent()->getEntryBlock().begin()); 6740a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman NewCI->takeName(CI); 6840a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman CI->replaceAllUsesWith(NewCI); 6940a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman return NewCI; 703913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz } 713913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz return CI; 72ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 7340a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman 74cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *I = CastInst::Create(opcode, V, Ty, V->getName(), 75cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman A->getParent()->getEntryBlock().begin()); 76cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(I); 77cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman return I; 78ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 793913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz 80ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner Instruction *I = cast<Instruction>(V); 813913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz 82ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner // Check to see if there is already a cast. If there is, use it. 83ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 84ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner UI != E; ++UI) { 85ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if ((*UI)->getType() == Ty) 863913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (CastInst *CI = dyn_cast<CastInst>(cast<Instruction>(*UI))) 873913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (CI->getOpcode() == opcode) { 883913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz BasicBlock::iterator It = I; ++It; 893913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (isa<InvokeInst>(I)) 903913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz It = cast<InvokeInst>(I)->getNormalDest()->begin(); 913913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz while (isa<PHINode>(It)) ++It; 923913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (It != BasicBlock::iterator(CI)) { 9340a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman // Recreate the cast at the beginning of the entry block. 9440a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman // The old cast is left in place in case it is being used 9540a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman // as an insert point. 9640a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman Instruction *NewCI = CastInst::Create(opcode, V, Ty, "", It); 9740a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman NewCI->takeName(CI); 9840a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman CI->replaceAllUsesWith(NewCI); 9940a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman return NewCI; 1003913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz } 1013913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz return CI; 102ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 103ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 104ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner BasicBlock::iterator IP = I; ++IP; 105ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if (InvokeInst *II = dyn_cast<InvokeInst>(I)) 106ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner IP = II->getNormalDest()->begin(); 107ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner while (isa<PHINode>(IP)) ++IP; 108cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *CI = CastInst::Create(opcode, V, Ty, V->getName(), IP); 109cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(CI); 110cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman return CI; 111ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner} 112ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner 113af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman/// InsertNoopCastOfTo - Insert a cast of V to the specified type, 114af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman/// which must be possible with a noop cast. 115af79fb5f47b0088c6a8973a7fdbaea96973a429dDan GohmanValue *SCEVExpander::InsertNoopCastOfTo(Value *V, const Type *Ty) { 116af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman Instruction::CastOps Op = CastInst::getCastOpcode(V, false, Ty, false); 117af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman assert((Op == Instruction::BitCast || 118e2a17468d1e47ef430933b7a91c5c1c4669d7d8dDevang Patel Op == Instruction::PtrToInt || 119e2a17468d1e47ef430933b7a91c5c1c4669d7d8dDevang Patel Op == Instruction::IntToPtr) && 120af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman "InsertNoopCastOfTo cannot perform non-noop casts!"); 121af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman assert(SE.getTypeSizeInBits(V->getType()) == SE.getTypeSizeInBits(Ty) && 122af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman "InsertNoopCastOfTo cannot change sizes!"); 123af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman return InsertCastOfTo(Op, V, Ty); 124af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman} 125af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman 1267fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner/// InsertBinop - Insert the specified binary operator, doing a small amount 1277fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner/// of work to avoid inserting an obviously redundant operation. 1287fec90ebf4ebe7aa73a6dd7d275c255587c041adChris LattnerValue *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, 1296cdc727f2d7f68734526ef078f4632798ad40791Dan Gohman Value *RHS, BasicBlock::iterator InsertPt) { 1300f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman // Fold a binop with constant operands. 1310f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman if (Constant *CLHS = dyn_cast<Constant>(LHS)) 1320f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman if (Constant *CRHS = dyn_cast<Constant>(RHS)) 1330f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman return ConstantExpr::get(Opcode, CLHS, CRHS); 1340f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman 1357fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner // Do a quick scan to see if we have this binop nearby. If so, reuse it. 1367fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner unsigned ScanLimit = 6; 1378a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz BasicBlock::iterator BlockBegin = InsertPt->getParent()->begin(); 1388a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz if (InsertPt != BlockBegin) { 1398a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz // Scanning starts from the last instruction before InsertPt. 1408a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz BasicBlock::iterator IP = InsertPt; 1418a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz --IP; 1428a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz for (; ScanLimit; --IP, --ScanLimit) { 1435be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (IP->getOpcode() == (unsigned)Opcode && IP->getOperand(0) == LHS && 1445be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman IP->getOperand(1) == RHS) 1455be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman return IP; 1468a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz if (IP == BlockBegin) break; 1478a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz } 1487fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner } 1498a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz 1508a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz // If we haven't found this binop, insert it. 151cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *BO = BinaryOperator::Create(Opcode, LHS, RHS, "tmp", InsertPt); 152cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(BO); 153cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman return BO; 1547fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner} 1557fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner 1564a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman/// FactorOutConstant - Test if S is divisible by Factor, using signed 157453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// division. If so, update S with Factor divided out and return true. 1584a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman/// S need not be evenly divisble if a reasonable remainder can be 1594a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman/// computed. 160453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// TODO: When ScalarEvolution gets a SCEVSDivExpr, this can be made 161453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// unnecessary; in its place, just signed-divide Ops[i] by the scale and 162453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// check to see if the divide was folded. 163372b46cad9f745859f542f9d2216991585ae83f4Owen Andersonstatic bool FactorOutConstant(const SCEV* &S, 164372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* &Remainder, 165453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman const APInt &Factor, 166453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman ScalarEvolution &SE) { 167453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // Everything is divisible by one. 168453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (Factor == 1) 169453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman return true; 170453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman 171453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // For a Constant, check for a multiple of the given factor. 1724a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) { 1734a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman ConstantInt *CI = 1744a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman ConstantInt::get(C->getValue()->getValue().sdiv(Factor)); 1754a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman // If the quotient is zero and the remainder is non-zero, reject 1764a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman // the value at this scale. It will be considered for subsequent 1774a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman // smaller scales. 1784a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman if (C->isZero() || !CI->isZero()) { 179372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* Div = SE.getConstant(CI); 180453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman S = Div; 1814a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman Remainder = 1824a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman SE.getAddExpr(Remainder, 1834a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman SE.getConstant(C->getValue()->getValue().srem(Factor))); 184453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman return true; 185453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 1864a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman } 187453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman 188453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // In a Mul, check if there is a constant operand which is a multiple 189453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // of the given factor. 190453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) 191453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (const SCEVConstant *C = dyn_cast<SCEVConstant>(M->getOperand(0))) 192453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (!C->getValue()->getValue().srem(Factor)) { 193372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SmallVectorImpl<const SCEV*> &MOperands = M->getOperands(); 194372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson SmallVector<const SCEV*, 4> NewMulOps(MOperands.begin(), MOperands.end()); 195453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman NewMulOps[0] = 196453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman SE.getConstant(C->getValue()->getValue().sdiv(Factor)); 197453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman S = SE.getMulExpr(NewMulOps); 198453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman return true; 199453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 200453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman 201453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // In an AddRec, check if both start and step are divisible. 202453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) { 203372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* Step = A->getStepRecurrence(SE); 204372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* StepRem = SE.getIntegerSCEV(0, Step->getType()); 2054a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman if (!FactorOutConstant(Step, StepRem, Factor, SE)) 2064a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman return false; 2074a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman if (!StepRem->isZero()) 2084a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman return false; 209372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* Start = A->getStart(); 2104a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman if (!FactorOutConstant(Start, Remainder, Factor, SE)) 211453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman return false; 212453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman S = SE.getAddRecExpr(Start, Step, A->getLoop()); 213453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman return true; 214453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 215453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman 216453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman return false; 217453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman} 218453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman 2195be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman/// expandAddToGEP - Expand a SCEVAddExpr with a pointer type into a GEP 220453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// instead of using ptrtoint+arithmetic+inttoptr. This helps 221453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// BasicAliasAnalysis analyze the result. However, it suffers from the 222453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// underlying bug described in PR2831. Addition in LLVM currently always 223453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// has two's complement wrapping guaranteed. However, the semantics for 224453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// getelementptr overflow are ambiguous. In the common case though, this 225453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// expansion gets used when a GEP in the original code has been converted 226453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// into integer arithmetic, in which case the resulting code will be no 227453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// more undefined than it was originally. 228453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// 229453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// Design note: It might seem desirable for this function to be more 230453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// loop-aware. If some of the indices are loop-invariant while others 231453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// aren't, it might seem desirable to emit multiple GEPs, keeping the 232453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// loop-invariant portions of the overall computation outside the loop. 233453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// However, there are a few reasons this is not done here. Hoisting simple 234453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// arithmetic is a low-level optimization that often isn't very 235453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// important until late in the optimization process. In fact, passes 236453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// like InstructionCombining will combine GEPs, even if it means 237453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// pushing loop-invariant computation down into loops, so even if the 238453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// GEPs were split here, the work would quickly be undone. The 239453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// LoopStrengthReduction pass, which is usually run quite late (and 240453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// after the last InstructionCombining pass), takes care of hoisting 241453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// loop-invariant portions of expressions, after considering what 242453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// can be folded using target addressing modes. 243453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// 244372b46cad9f745859f542f9d2216991585ae83f4Owen AndersonValue *SCEVExpander::expandAddToGEP(const SCEV* const *op_begin, 245372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* const *op_end, 2465be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman const PointerType *PTy, 2475be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman const Type *Ty, 2485be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Value *V) { 2495be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman const Type *ElTy = PTy->getElementType(); 2505be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman SmallVector<Value *, 4> GepIndices; 251372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson SmallVector<const SCEV*, 8> Ops(op_begin, op_end); 2525be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman bool AnyNonZeroIndices = false; 2535be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 2545be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // Decend down the pointer's type and attempt to convert the other 2555be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // operands into GEP indices, at each level. The first index in a GEP 2565be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // indexes into the array implied by the pointer operand; the rest of 2575be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // the indices index into the element or field type selected by the 2585be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // preceding index. 2595be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman for (;;) { 2605be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman APInt ElSize = APInt(SE.getTypeSizeInBits(Ty), 2615be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman ElTy->isSized() ? SE.TD->getTypeAllocSize(ElTy) : 0); 262372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson SmallVector<const SCEV*, 8> NewOps; 263372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson SmallVector<const SCEV*, 8> ScaledOps; 2645be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 265453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // Split AddRecs up into parts as either of the parts may be usable 266453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // without the other. 267453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Ops[i])) 268453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (!A->getStart()->isZero()) { 269372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* Start = A->getStart(); 270453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman Ops.push_back(SE.getAddRecExpr(SE.getIntegerSCEV(0, A->getType()), 271453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman A->getStepRecurrence(SE), 272453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman A->getLoop())); 273453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman Ops[i] = Start; 274453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman ++e; 275453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 276453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // If the scale size is not 0, attempt to factor out a scale. 2775be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (ElSize != 0) { 278372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* Op = Ops[i]; 279372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* Remainder = SE.getIntegerSCEV(0, Op->getType()); 2804a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman if (FactorOutConstant(Op, Remainder, ElSize, SE)) { 281453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman ScaledOps.push_back(Op); // Op now has ElSize factored out. 2824a4f767235dac50965fc266fb822d9a2e37d5212Dan Gohman NewOps.push_back(Remainder); 2835be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman continue; 2845be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 2855be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 286453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // If the operand was not divisible, add it to the list of operands 287453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // we'll scan next iteration. 2885be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman NewOps.push_back(Ops[i]); 2895be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 2905be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Ops = NewOps; 2915be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman AnyNonZeroIndices |= !ScaledOps.empty(); 2925be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Value *Scaled = ScaledOps.empty() ? 2935be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Constant::getNullValue(Ty) : 2945be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman expandCodeFor(SE.getAddExpr(ScaledOps), Ty); 2955be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman GepIndices.push_back(Scaled); 2965be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 2975be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // Collect struct field index operands. 2985be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (!Ops.empty()) 2995be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman while (const StructType *STy = dyn_cast<StructType>(ElTy)) { 3005be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[0])) 3015be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (SE.getTypeSizeInBits(C->getType()) <= 64) { 3025be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman const StructLayout &SL = *SE.TD->getStructLayout(STy); 3035be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman uint64_t FullOffset = C->getValue()->getZExtValue(); 3045be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (FullOffset < SL.getSizeInBytes()) { 3055be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman unsigned ElIdx = SL.getElementContainingOffset(FullOffset); 3065be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman GepIndices.push_back(ConstantInt::get(Type::Int32Ty, ElIdx)); 3075be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman ElTy = STy->getTypeAtIndex(ElIdx); 3085be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Ops[0] = 3096de29f8d960505421d61c80cdb738e16720b6c0eDan Gohman SE.getConstant(Ty, FullOffset - SL.getElementOffset(ElIdx)); 3105be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman AnyNonZeroIndices = true; 3115be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman continue; 3125be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 3135be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 3145be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman break; 3155be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 3165be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 3175be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (const ArrayType *ATy = dyn_cast<ArrayType>(ElTy)) { 3185be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman ElTy = ATy->getElementType(); 3195be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman continue; 3205be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 3215be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman break; 3225be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 3235be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 3245be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // If none of the operands were convertable to proper GEP indices, cast 3255be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // the base to i8* and do an ugly getelementptr with that. It's still 3265be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // better than ptrtoint+arithmetic+inttoptr at least. 3275be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (!AnyNonZeroIndices) { 3285be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman V = InsertNoopCastOfTo(V, 3295be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Type::Int8Ty->getPointerTo(PTy->getAddressSpace())); 33092fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *Idx = expandCodeFor(SE.getAddExpr(Ops), Ty); 3315be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 3325be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // Fold a GEP with constant operands. 3335be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (Constant *CLHS = dyn_cast<Constant>(V)) 3345be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (Constant *CRHS = dyn_cast<Constant>(Idx)) 335278b49af8a08f6ab6c486a3cfc7a9c1c1acd2b23Dan Gohman return ConstantExpr::getGetElementPtr(CLHS, &CRHS, 1); 3365be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 3375be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // Do a quick scan to see if we have this GEP nearby. If so, reuse it. 3385be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman unsigned ScanLimit = 6; 3395be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman BasicBlock::iterator BlockBegin = InsertPt->getParent()->begin(); 3405be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (InsertPt != BlockBegin) { 3415be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // Scanning starts from the last instruction before InsertPt. 3425be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman BasicBlock::iterator IP = InsertPt; 3435be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman --IP; 3445be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman for (; ScanLimit; --IP, --ScanLimit) { 3455be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (IP->getOpcode() == Instruction::GetElementPtr && 3465be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman IP->getOperand(0) == V && IP->getOperand(1) == Idx) 3475be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman return IP; 3485be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (IP == BlockBegin) break; 3495be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 3505be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 3515be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 3525be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Value *GEP = GetElementPtrInst::Create(V, Idx, "scevgep", InsertPt); 3535be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman InsertedValues.insert(GEP); 3545be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman return GEP; 3555be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 3565be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 3575be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // Insert a pretty getelementptr. 3585be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Value *GEP = GetElementPtrInst::Create(V, 3595be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman GepIndices.begin(), 3605be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman GepIndices.end(), 3615be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman "scevgep", InsertPt); 3625be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Ops.push_back(SE.getUnknown(GEP)); 3635be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman InsertedValues.insert(GEP); 3645be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman return expand(SE.getAddExpr(Ops)); 3655be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman} 3665be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 367890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitAddExpr(const SCEVAddExpr *S) { 368af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 369e24fa64d52330626553298f56ba5aa702624c282Dan Gohman Value *V = expand(S->getOperand(S->getNumOperands()-1)); 3705be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 371453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // Turn things like ptrtoint+arithmetic+inttoptr into GEP. See the 372453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // comments on expandAddToGEP for details. 3735be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (SE.TD) 374453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (const PointerType *PTy = dyn_cast<PointerType>(V->getType())) { 375372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SmallVectorImpl<const SCEV*> &Ops = S->getOperands(); 376fb5a3419f351056e0f599699d276bcab412d2cceDan Gohman return expandAddToGEP(&Ops[0], &Ops[Ops.size() - 1], 377453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman PTy, Ty, V); 378453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 3795be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 380af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman V = InsertNoopCastOfTo(V, Ty); 381e24fa64d52330626553298f56ba5aa702624c282Dan Gohman 382e24fa64d52330626553298f56ba5aa702624c282Dan Gohman // Emit a bunch of add instructions 3832d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman for (int i = S->getNumOperands()-2; i >= 0; --i) { 38492fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *W = expandCodeFor(S->getOperand(i), Ty); 3852d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman V = InsertBinop(Instruction::Add, V, W, InsertPt); 3862d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman } 387e24fa64d52330626553298f56ba5aa702624c282Dan Gohman return V; 388e24fa64d52330626553298f56ba5aa702624c282Dan Gohman} 3895be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 390890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) { 391af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 39236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman int FirstOp = 0; // Set if we should emit a subtract. 393890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getOperand(0))) 39436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman if (SC->getValue()->isAllOnesValue()) 39536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman FirstOp = 1; 39636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 39736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman int i = S->getNumOperands()-2; 39892fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *V = expandCodeFor(S->getOperand(i+1), Ty); 39936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 40036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // Emit a bunch of multiply instructions 4012d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman for (; i >= FirstOp; --i) { 40292fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *W = expandCodeFor(S->getOperand(i), Ty); 4032d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman V = InsertBinop(Instruction::Mul, V, W, InsertPt); 4042d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman } 4052d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman 40636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // -1 * ... ---> 0 - ... 40736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman if (FirstOp == 1) 4082d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman V = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), V, InsertPt); 40936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman return V; 41036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman} 41136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 412890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitUDivExpr(const SCEVUDivExpr *S) { 413af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 4142d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman 41592fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *LHS = expandCodeFor(S->getLHS(), Ty); 416890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getRHS())) { 4176177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky const APInt &RHS = SC->getValue()->getValue(); 4186177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky if (RHS.isPowerOf2()) 4196177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky return InsertBinop(Instruction::LShr, LHS, 4202d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman ConstantInt::get(Ty, RHS.logBase2()), 4216177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky InsertPt); 4226177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky } 4236177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky 42492fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *RHS = expandCodeFor(S->getRHS(), Ty); 4256177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky return InsertBinop(Instruction::UDiv, LHS, RHS, InsertPt); 4266177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky} 4276177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky 428453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// Move parts of Base into Rest to leave Base with the minimal 429453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// expression that provides a pointer operand suitable for a 430453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// GEP expansion. 431372b46cad9f745859f542f9d2216991585ae83f4Owen Andersonstatic void ExposePointerBase(const SCEV* &Base, const SCEV* &Rest, 432453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman ScalarEvolution &SE) { 433453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman while (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Base)) { 434453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman Base = A->getStart(); 435453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman Rest = SE.getAddExpr(Rest, 436453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman SE.getAddRecExpr(SE.getIntegerSCEV(0, A->getType()), 437453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman A->getStepRecurrence(SE), 438453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman A->getLoop())); 439453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 440453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(Base)) { 441453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman Base = A->getOperand(A->getNumOperands()-1); 442372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson SmallVector<const SCEV*, 8> NewAddOps(A->op_begin(), A->op_end()); 443453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman NewAddOps.back() = Rest; 444453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman Rest = SE.getAddExpr(NewAddOps); 445453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman ExposePointerBase(Base, Rest, SE); 446453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 447453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman} 448453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman 449890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) { 450af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 45136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman const Loop *L = S->getLoop(); 45236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 4534d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // First check for an existing canonical IV in a suitable type. 4544d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman PHINode *CanonicalIV = 0; 4554d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman if (PHINode *PN = L->getCanonicalInductionVariable()) 4564d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman if (SE.isSCEVable(PN->getType()) && 4574d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman isa<IntegerType>(SE.getEffectiveSCEVType(PN->getType())) && 4584d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman SE.getTypeSizeInBits(PN->getType()) >= SE.getTypeSizeInBits(Ty)) 4594d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman CanonicalIV = PN; 4604d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 4614d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // Rewrite an AddRec in terms of the canonical induction variable, if 4624d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // its type is more narrow. 4634d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman if (CanonicalIV && 4644d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman SE.getTypeSizeInBits(CanonicalIV->getType()) > 4654d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman SE.getTypeSizeInBits(Ty)) { 466372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* Start = SE.getAnyExtendExpr(S->getStart(), 4674d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman CanonicalIV->getType()); 468372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* Step = SE.getAnyExtendExpr(S->getStepRecurrence(SE), 4694d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman CanonicalIV->getType()); 4704d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman Value *V = expand(SE.getAddRecExpr(Start, Step, S->getLoop())); 4714d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman BasicBlock::iterator SaveInsertPt = getInsertionPoint(); 4724d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman BasicBlock::iterator NewInsertPt = 4734d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman next(BasicBlock::iterator(cast<Instruction>(V))); 4744d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman while (isa<PHINode>(NewInsertPt)) ++NewInsertPt; 4754d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman V = expandCodeFor(SE.getTruncateExpr(SE.getUnknown(V), Ty), 0, 4764d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman NewInsertPt); 4774d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman setInsertionPoint(SaveInsertPt); 4784d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman return V; 4794d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman } 4804d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 48136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // {X,+,F} --> X + {0,+,F} 482cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman if (!S->getStart()->isZero()) { 483372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SmallVectorImpl<const SCEV*> &SOperands = S->getOperands(); 484372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson SmallVector<const SCEV*, 4> NewOps(SOperands.begin(), SOperands.end()); 485246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman NewOps[0] = SE.getIntegerSCEV(0, Ty); 486372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* Rest = SE.getAddRecExpr(NewOps, L); 487453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman 488453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // Turn things like ptrtoint+arithmetic+inttoptr into GEP. See the 489453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // comments on expandAddToGEP for details. 490453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (SE.TD) { 491372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* Base = S->getStart(); 492372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* RestArray[1] = { Rest }; 493453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // Dig into the expression to find the pointer base for a GEP. 494453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman ExposePointerBase(Base, RestArray[0], SE); 495453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // If we found a pointer, expand the AddRec with a GEP. 496453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (const PointerType *PTy = dyn_cast<PointerType>(Base->getType())) { 497f876ad0a70c5c3bb402de2766237410f041700e6Dan Gohman // Make sure the Base isn't something exotic, such as a multiplied 498f876ad0a70c5c3bb402de2766237410f041700e6Dan Gohman // or divided pointer value. In those cases, the result type isn't 499f876ad0a70c5c3bb402de2766237410f041700e6Dan Gohman // actually a pointer type. 500f876ad0a70c5c3bb402de2766237410f041700e6Dan Gohman if (!isa<SCEVMulExpr>(Base) && !isa<SCEVUDivExpr>(Base)) { 501f876ad0a70c5c3bb402de2766237410f041700e6Dan Gohman Value *StartV = expand(Base); 502f876ad0a70c5c3bb402de2766237410f041700e6Dan Gohman assert(StartV->getType() == PTy && "Pointer type mismatch for GEP!"); 503f876ad0a70c5c3bb402de2766237410f041700e6Dan Gohman return expandAddToGEP(RestArray, RestArray+1, PTy, Ty, StartV); 504f876ad0a70c5c3bb402de2766237410f041700e6Dan Gohman } 505453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 506453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 507453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman 50840a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman // Just do a normal add. Pre-expand the operands to suppress folding. 50940a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman return expand(SE.getAddExpr(SE.getUnknown(expand(S->getStart())), 51040a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman SE.getUnknown(expand(Rest)))); 51136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman } 51236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 51336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // {0,+,1} --> Insert a canonical induction variable into the loop! 51417f1972c770dc18f5c7c3c95776b4d62ae9e121dDan Gohman if (S->isAffine() && 515246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman S->getOperand(1) == SE.getIntegerSCEV(1, Ty)) { 5164d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // If there's a canonical IV, just use it. 5174d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman if (CanonicalIV) { 5184d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman assert(Ty == SE.getEffectiveSCEVType(CanonicalIV->getType()) && 5194d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman "IVs with types different from the canonical IV should " 5204d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman "already have been handled!"); 5214d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman return CanonicalIV; 5224d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman } 5234d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 52436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // Create and insert the PHI node for the induction variable in the 52536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // specified loop. 52636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman BasicBlock *Header = L->getHeader(); 527051a950000e21935165db56695e35bade668193bGabor Greif PHINode *PN = PHINode::Create(Ty, "indvar", Header->begin()); 528cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(PN); 52936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman PN->addIncoming(Constant::getNullValue(Ty), L->getLoopPreheader()); 53036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 53136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman pred_iterator HPI = pred_begin(Header); 53236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman assert(HPI != pred_end(Header) && "Loop with zero preds???"); 53336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman if (!L->contains(*HPI)) ++HPI; 53436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman assert(HPI != pred_end(Header) && L->contains(*HPI) && 53536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman "No backedge in loop?"); 53636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 53736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // Insert a unit add instruction right before the terminator corresponding 53836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // to the back-edge. 53924d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer Constant *One = ConstantInt::get(Ty, 1); 5407cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Instruction *Add = BinaryOperator::CreateAdd(PN, One, "indvar.next", 54136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman (*HPI)->getTerminator()); 542cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(Add); 54336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 54436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman pred_iterator PI = pred_begin(Header); 54536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman if (*PI == L->getLoopPreheader()) 54636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman ++PI; 54736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman PN->addIncoming(Add, *PI); 54836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman return PN; 54936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman } 55036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 5514d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // {0,+,F} --> {0,+,1} * F 55236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // Get the canonical induction variable I for this loop. 5534d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman Value *I = CanonicalIV ? 5544d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman CanonicalIV : 5554d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman getOrInsertCanonicalInductionVariable(L, Ty); 55636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 557df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // If this is a simple linear addrec, emit it now as a special case. 55840a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman if (S->isAffine()) // {0,+,F} --> i*F 55940a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman return 56040a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman expand(SE.getTruncateOrNoop( 56140a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman SE.getMulExpr(SE.getUnknown(I), 56240a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman SE.getNoopOrAnyExtend(S->getOperand(1), 56340a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman I->getType())), 56440a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman Ty)); 56536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 56636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // If this is a chain of recurrences, turn it into a closed form, using the 56736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // folders, then expandCodeFor the closed form. This allows the folders to 56836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // simplify the expression without having to build a bunch of special code 56936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // into this folder. 570372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* IH = SE.getUnknown(I); // Get I as a "symbolic" SCEV. 57136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 5724d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // Promote S up to the canonical IV type, if the cast is foldable. 573372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* NewS = S; 574372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* Ext = SE.getNoopOrAnyExtend(S, I->getType()); 5754d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman if (isa<SCEVAddRecExpr>(Ext)) 5764d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman NewS = Ext; 5774d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman 578372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* V = cast<SCEVAddRecExpr>(NewS)->evaluateAtIteration(IH, SE); 579e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling //cerr << "Evaluated: " << *this << "\n to: " << *V << "\n"; 58036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 5814d8414f42033a5e744e8e60d2ca188b424c76168Dan Gohman // Truncate the result down to the original type, if needed. 582372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* T = SE.getTruncateOrNoop(V, Ty); 583469f3cdc13851914f3a766cbd8f701cf8431cacaDan Gohman return expand(T); 58436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman} 58596fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov 586890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitTruncateExpr(const SCEVTruncateExpr *S) { 587af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 58892fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *V = expandCodeFor(S->getOperand(), 58992fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman SE.getEffectiveSCEVType(S->getOperand()->getType())); 590cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *I = new TruncInst(V, Ty, "tmp.", InsertPt); 591cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(I); 592cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman return I; 59311f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman} 59411f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman 595890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitZeroExtendExpr(const SCEVZeroExtendExpr *S) { 596af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 59792fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *V = expandCodeFor(S->getOperand(), 59892fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman SE.getEffectiveSCEVType(S->getOperand()->getType())); 599cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *I = new ZExtInst(V, Ty, "tmp.", InsertPt); 600cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(I); 601cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman return I; 60211f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman} 60311f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman 604890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitSignExtendExpr(const SCEVSignExtendExpr *S) { 605af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 60692fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *V = expandCodeFor(S->getOperand(), 60792fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman SE.getEffectiveSCEVType(S->getOperand()->getType())); 608cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *I = new SExtInst(V, Ty, "tmp.", InsertPt); 609cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(I); 610cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman return I; 61111f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman} 61211f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman 613890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitSMaxExpr(const SCEVSMaxExpr *S) { 614af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 61592fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *LHS = expandCodeFor(S->getOperand(0), Ty); 616c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky for (unsigned i = 1; i < S->getNumOperands(); ++i) { 61792fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *RHS = expandCodeFor(S->getOperand(i), Ty); 618cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *ICmp = 619cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman new ICmpInst(ICmpInst::ICMP_SGT, LHS, RHS, "tmp", InsertPt); 620cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(ICmp); 621cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *Sel = SelectInst::Create(ICmp, LHS, RHS, "smax", InsertPt); 622cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(Sel); 623cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman LHS = Sel; 624c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky } 625c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky return LHS; 626c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky} 627c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky 628890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitUMaxExpr(const SCEVUMaxExpr *S) { 629af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 63092fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *LHS = expandCodeFor(S->getOperand(0), Ty); 6313e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky for (unsigned i = 1; i < S->getNumOperands(); ++i) { 63292fcdcac543653a62949fe9e5a7bd008500c1380Dan Gohman Value *RHS = expandCodeFor(S->getOperand(i), Ty); 633cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *ICmp = 634cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman new ICmpInst(ICmpInst::ICMP_UGT, LHS, RHS, "tmp", InsertPt); 635cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(ICmp); 636cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *Sel = SelectInst::Create(ICmp, LHS, RHS, "umax", InsertPt); 637cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(Sel); 638cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman LHS = Sel; 6393e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky } 6403e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky return LHS; 6413e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky} 6423e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky 643372b46cad9f745859f542f9d2216991585ae83f4Owen AndersonValue *SCEVExpander::expandCodeFor(const SCEV* SH, const Type *Ty) { 64411f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman // Expand the code for this SCEV. 6452d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman Value *V = expand(SH); 6465be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (Ty) { 6475be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman assert(SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType()) && 6485be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman "non-trivial casts should be done with the SCEVs directly!"); 6495be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman V = InsertNoopCastOfTo(V, Ty); 6505be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 6515be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman return V; 65211f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman} 65311f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman 654890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::expand(const SCEV *S) { 65596fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov // Check to see if we already expanded this. 656372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson std::map<const SCEV*, AssertingVH<Value> >::iterator I = 6573790fb0c036acaa4db50aff83dd8b3bf51f8af6aTorok Edwin InsertedExpressions.find(S); 65896fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov if (I != InsertedExpressions.end()) 65996fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov return I->second; 66040a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman 66140a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman // Compute an insertion point for this SCEV object. Hoist the instructions 66240a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman // as far out in the loop nest as possible. 66340a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman BasicBlock::iterator InsertPt = getInsertionPoint(); 66440a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman BasicBlock::iterator SaveInsertPt = InsertPt; 66540a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman for (Loop *L = SE.LI->getLoopFor(InsertPt->getParent()); ; 66640a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman L = L->getParentLoop()) 66740a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman if (S->isLoopInvariant(L)) { 66840a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman if (!L) break; 66940a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman if (BasicBlock *Preheader = L->getLoopPreheader()) 67040a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman InsertPt = Preheader->getTerminator(); 67140a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman } else { 67240a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman // If the SCEV is computable at this level, insert it into the header 67340a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman // after the PHIs (and after any other instructions that we've inserted 67440a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman // there) so that it is guaranteed to dominate any user inside the loop. 67540a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman if (L && S->hasComputableLoopEvolution(L)) 67640a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman InsertPt = L->getHeader()->getFirstNonPHI(); 67740a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman while (isInsertedInstruction(InsertPt)) ++InsertPt; 67840a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman break; 67940a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman } 68040a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman setInsertionPoint(InsertPt); 68140a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman 68296fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov Value *V = visit(S); 68340a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman 68440a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman setInsertionPoint(SaveInsertPt); 68596fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov InsertedExpressions[S] = V; 68696fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov return V; 68796fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov} 6881d09de3eca23267855e28297fcb40de3632ea47bDan Gohman 6891d09de3eca23267855e28297fcb40de3632ea47bDan Gohman/// getOrInsertCanonicalInductionVariable - This method returns the 6901d09de3eca23267855e28297fcb40de3632ea47bDan Gohman/// canonical induction variable of the specified type for the specified 6911d09de3eca23267855e28297fcb40de3632ea47bDan Gohman/// loop (inserting one if there is none). A canonical induction variable 6921d09de3eca23267855e28297fcb40de3632ea47bDan Gohman/// starts at zero and steps by one on each iteration. 6931d09de3eca23267855e28297fcb40de3632ea47bDan GohmanValue * 6941d09de3eca23267855e28297fcb40de3632ea47bDan GohmanSCEVExpander::getOrInsertCanonicalInductionVariable(const Loop *L, 6951d09de3eca23267855e28297fcb40de3632ea47bDan Gohman const Type *Ty) { 6961d09de3eca23267855e28297fcb40de3632ea47bDan Gohman assert(Ty->isInteger() && "Can only insert integer induction variables!"); 697372b46cad9f745859f542f9d2216991585ae83f4Owen Anderson const SCEV* H = SE.getAddRecExpr(SE.getIntegerSCEV(0, Ty), 69840a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman SE.getIntegerSCEV(1, Ty), L); 69940a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman BasicBlock::iterator SaveInsertPt = getInsertionPoint(); 70040a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman Value *V = expandCodeFor(H, 0, L->getHeader()->begin()); 70140a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman setInsertionPoint(SaveInsertPt); 70240a5a1b39ee1cd40ff9d04740386b667fb27b340Dan Gohman return V; 7031d09de3eca23267855e28297fcb40de3632ea47bDan Gohman} 704