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