ScalarEvolutionExpander.cpp revision f876ad0a70c5c3bb402de2766237410f041700e6
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" 1936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begemanusing namespace llvm; 2036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 21ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner/// InsertCastOfTo - Insert a cast of V to the specified type, doing what 22ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner/// we can to share the casts. 233ba68b9eef2851dae8a9d1b18928c6fa2e3c5f87Reid SpencerValue *SCEVExpander::InsertCastOfTo(Instruction::CastOps opcode, Value *V, 243ba68b9eef2851dae8a9d1b18928c6fa2e3c5f87Reid Spencer const Type *Ty) { 252d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman // Short-circuit unnecessary bitcasts. 262d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman if (opcode == Instruction::BitCast && V->getType() == Ty) 272d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman return V; 282d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman 29f04fa483b83227c570bc58e1684ea096430a6697Dan Gohman // Short-circuit unnecessary inttoptr<->ptrtoint casts. 30af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman if ((opcode == Instruction::PtrToInt || opcode == Instruction::IntToPtr) && 3180dcdee0f48820ecea86c15768324945bb0d68d1Dan Gohman SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(V->getType())) { 32af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman if (CastInst *CI = dyn_cast<CastInst>(V)) 33af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman if ((CI->getOpcode() == Instruction::PtrToInt || 34af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman CI->getOpcode() == Instruction::IntToPtr) && 35af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman SE.getTypeSizeInBits(CI->getType()) == 36af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman SE.getTypeSizeInBits(CI->getOperand(0)->getType())) 37af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman return CI->getOperand(0); 3880dcdee0f48820ecea86c15768324945bb0d68d1Dan Gohman if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) 3980dcdee0f48820ecea86c15768324945bb0d68d1Dan Gohman if ((CE->getOpcode() == Instruction::PtrToInt || 4080dcdee0f48820ecea86c15768324945bb0d68d1Dan Gohman CE->getOpcode() == Instruction::IntToPtr) && 4180dcdee0f48820ecea86c15768324945bb0d68d1Dan Gohman SE.getTypeSizeInBits(CE->getType()) == 4280dcdee0f48820ecea86c15768324945bb0d68d1Dan Gohman SE.getTypeSizeInBits(CE->getOperand(0)->getType())) 4380dcdee0f48820ecea86c15768324945bb0d68d1Dan Gohman return CE->getOperand(0); 4480dcdee0f48820ecea86c15768324945bb0d68d1Dan Gohman } 45f04fa483b83227c570bc58e1684ea096430a6697Dan Gohman 46ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner // FIXME: keep track of the cast instruction. 47ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if (Constant *C = dyn_cast<Constant>(V)) 48d977d8651a5cd26a3e1088267f31cade405f2adfReid Spencer return ConstantExpr::getCast(opcode, C, Ty); 49ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner 50ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if (Argument *A = dyn_cast<Argument>(V)) { 51ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner // Check to see if there is already a cast! 52ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner for (Value::use_iterator UI = A->use_begin(), E = A->use_end(); 53ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner UI != E; ++UI) { 54ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if ((*UI)->getType() == Ty) 553913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (CastInst *CI = dyn_cast<CastInst>(cast<Instruction>(*UI))) 563913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (CI->getOpcode() == opcode) { 573913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz // If the cast isn't the first instruction of the function, move it. 583913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (BasicBlock::iterator(CI) != 593913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz A->getParent()->getEntryBlock().begin()) { 60aabb04f52714ceb271dba7da18f757a4365bb4acDan Gohman // If the CastInst is the insert point, change the insert point. 61aabb04f52714ceb271dba7da18f757a4365bb4acDan Gohman if (CI == InsertPt) ++InsertPt; 62aabb04f52714ceb271dba7da18f757a4365bb4acDan Gohman // Splice the cast at the beginning of the entry block. 633913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz CI->moveBefore(A->getParent()->getEntryBlock().begin()); 643913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz } 653913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz return CI; 66ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 67ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 68cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *I = CastInst::Create(opcode, V, Ty, V->getName(), 69cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman A->getParent()->getEntryBlock().begin()); 70cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(I); 71cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman return I; 72ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 733913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz 74ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner Instruction *I = cast<Instruction>(V); 753913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz 76ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner // Check to see if there is already a cast. If there is, use it. 77ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); 78ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner UI != E; ++UI) { 79ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if ((*UI)->getType() == Ty) 803913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (CastInst *CI = dyn_cast<CastInst>(cast<Instruction>(*UI))) 813913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (CI->getOpcode() == opcode) { 823913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz BasicBlock::iterator It = I; ++It; 833913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (isa<InvokeInst>(I)) 843913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz It = cast<InvokeInst>(I)->getNormalDest()->begin(); 853913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz while (isa<PHINode>(It)) ++It; 863913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz if (It != BasicBlock::iterator(CI)) { 87aabb04f52714ceb271dba7da18f757a4365bb4acDan Gohman // If the CastInst is the insert point, change the insert point. 88aabb04f52714ceb271dba7da18f757a4365bb4acDan Gohman if (CI == InsertPt) ++InsertPt; 893913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz // Splice the cast immediately after the operand in question. 903913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz CI->moveBefore(It); 913913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz } 923913187bf6135e6a71260c65eed664095c8f9ce9Wojciech Matyjewicz return CI; 93ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 94ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner } 95ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner BasicBlock::iterator IP = I; ++IP; 96ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner if (InvokeInst *II = dyn_cast<InvokeInst>(I)) 97ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner IP = II->getNormalDest()->begin(); 98ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner while (isa<PHINode>(IP)) ++IP; 99cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *CI = CastInst::Create(opcode, V, Ty, V->getName(), IP); 100cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(CI); 101cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman return CI; 102ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner} 103ca1a4bebb3928ba18fb8751e2f0c0f88fad54cfdChris Lattner 104af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman/// InsertNoopCastOfTo - Insert a cast of V to the specified type, 105af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman/// which must be possible with a noop cast. 106af79fb5f47b0088c6a8973a7fdbaea96973a429dDan GohmanValue *SCEVExpander::InsertNoopCastOfTo(Value *V, const Type *Ty) { 107af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman Instruction::CastOps Op = CastInst::getCastOpcode(V, false, Ty, false); 108af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman assert((Op == Instruction::BitCast || 109e2a17468d1e47ef430933b7a91c5c1c4669d7d8dDevang Patel Op == Instruction::PtrToInt || 110e2a17468d1e47ef430933b7a91c5c1c4669d7d8dDevang Patel Op == Instruction::IntToPtr) && 111af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman "InsertNoopCastOfTo cannot perform non-noop casts!"); 112af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman assert(SE.getTypeSizeInBits(V->getType()) == SE.getTypeSizeInBits(Ty) && 113af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman "InsertNoopCastOfTo cannot change sizes!"); 114af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman return InsertCastOfTo(Op, V, Ty); 115af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman} 116af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman 1177fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner/// InsertBinop - Insert the specified binary operator, doing a small amount 1187fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner/// of work to avoid inserting an obviously redundant operation. 1197fec90ebf4ebe7aa73a6dd7d275c255587c041adChris LattnerValue *SCEVExpander::InsertBinop(Instruction::BinaryOps Opcode, Value *LHS, 1206cdc727f2d7f68734526ef078f4632798ad40791Dan Gohman Value *RHS, BasicBlock::iterator InsertPt) { 1210f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman // Fold a binop with constant operands. 1220f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman if (Constant *CLHS = dyn_cast<Constant>(LHS)) 1230f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman if (Constant *CRHS = dyn_cast<Constant>(RHS)) 1240f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman return ConstantExpr::get(Opcode, CLHS, CRHS); 1250f0eb18addc94bf3d8179fbce162c8c4622b9866Dan Gohman 1267fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner // Do a quick scan to see if we have this binop nearby. If so, reuse it. 1277fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner unsigned ScanLimit = 6; 1288a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz BasicBlock::iterator BlockBegin = InsertPt->getParent()->begin(); 1298a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz if (InsertPt != BlockBegin) { 1308a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz // Scanning starts from the last instruction before InsertPt. 1318a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz BasicBlock::iterator IP = InsertPt; 1328a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz --IP; 1338a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz for (; ScanLimit; --IP, --ScanLimit) { 1345be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (IP->getOpcode() == (unsigned)Opcode && IP->getOperand(0) == LHS && 1355be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman IP->getOperand(1) == RHS) 1365be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman return IP; 1378a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz if (IP == BlockBegin) break; 1388a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz } 1397fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner } 1408a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz 1418a08769bad43a22fae2845bb0ba0fd1266cd55c8Wojciech Matyjewicz // If we haven't found this binop, insert it. 142cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *BO = BinaryOperator::Create(Opcode, LHS, RHS, "tmp", InsertPt); 143cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(BO); 144cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman return BO; 1457fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner} 1467fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner 147453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// FactorOutConstant - Test if S is evenly divisible by Factor, using signed 148453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// division. If so, update S with Factor divided out and return true. 149453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// TODO: When ScalarEvolution gets a SCEVSDivExpr, this can be made 150453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// unnecessary; in its place, just signed-divide Ops[i] by the scale and 151453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// check to see if the divide was folded. 152453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohmanstatic bool FactorOutConstant(SCEVHandle &S, 153453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman const APInt &Factor, 154453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman ScalarEvolution &SE) { 155453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // Everything is divisible by one. 156453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (Factor == 1) 157453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman return true; 158453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman 159453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // For a Constant, check for a multiple of the given factor. 160453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (const SCEVConstant *C = dyn_cast<SCEVConstant>(S)) 161453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (!C->getValue()->getValue().srem(Factor)) { 162453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman ConstantInt *CI = 163453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman ConstantInt::get(C->getValue()->getValue().sdiv(Factor)); 164453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman SCEVHandle Div = SE.getConstant(CI); 165453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman S = Div; 166453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman return true; 167453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 168453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman 169453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // In a Mul, check if there is a constant operand which is a multiple 170453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // of the given factor. 171453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(S)) 172453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (const SCEVConstant *C = dyn_cast<SCEVConstant>(M->getOperand(0))) 173453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (!C->getValue()->getValue().srem(Factor)) { 174453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman std::vector<SCEVHandle> NewMulOps(M->getOperands()); 175453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman NewMulOps[0] = 176453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman SE.getConstant(C->getValue()->getValue().sdiv(Factor)); 177453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman S = SE.getMulExpr(NewMulOps); 178453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman return true; 179453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 180453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman 181453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // In an AddRec, check if both start and step are divisible. 182453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(S)) { 183453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman SCEVHandle Start = A->getStart(); 184453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (!FactorOutConstant(Start, Factor, SE)) 185453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman return false; 186453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman SCEVHandle Step = A->getStepRecurrence(SE); 187453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (!FactorOutConstant(Step, Factor, SE)) 188453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman return false; 189453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman S = SE.getAddRecExpr(Start, Step, A->getLoop()); 190453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman return true; 191453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 192453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman 193453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman return false; 194453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman} 195453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman 1965be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman/// expandAddToGEP - Expand a SCEVAddExpr with a pointer type into a GEP 197453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// instead of using ptrtoint+arithmetic+inttoptr. This helps 198453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// BasicAliasAnalysis analyze the result. However, it suffers from the 199453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// underlying bug described in PR2831. Addition in LLVM currently always 200453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// has two's complement wrapping guaranteed. However, the semantics for 201453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// getelementptr overflow are ambiguous. In the common case though, this 202453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// expansion gets used when a GEP in the original code has been converted 203453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// into integer arithmetic, in which case the resulting code will be no 204453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// more undefined than it was originally. 205453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// 206453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// Design note: It might seem desirable for this function to be more 207453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// loop-aware. If some of the indices are loop-invariant while others 208453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// aren't, it might seem desirable to emit multiple GEPs, keeping the 209453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// loop-invariant portions of the overall computation outside the loop. 210453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// However, there are a few reasons this is not done here. Hoisting simple 211453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// arithmetic is a low-level optimization that often isn't very 212453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// important until late in the optimization process. In fact, passes 213453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// like InstructionCombining will combine GEPs, even if it means 214453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// pushing loop-invariant computation down into loops, so even if the 215453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// GEPs were split here, the work would quickly be undone. The 216453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// LoopStrengthReduction pass, which is usually run quite late (and 217453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// after the last InstructionCombining pass), takes care of hoisting 218453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// loop-invariant portions of expressions, after considering what 219453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// can be folded using target addressing modes. 220453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// 221453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan GohmanValue *SCEVExpander::expandAddToGEP(const SCEVHandle *op_begin, 222453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman const SCEVHandle *op_end, 2235be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman const PointerType *PTy, 2245be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman const Type *Ty, 2255be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Value *V) { 2265be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman const Type *ElTy = PTy->getElementType(); 2275be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman SmallVector<Value *, 4> GepIndices; 228453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman std::vector<SCEVHandle> Ops(op_begin, op_end); 2295be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman bool AnyNonZeroIndices = false; 2305be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 2315be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // Decend down the pointer's type and attempt to convert the other 2325be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // operands into GEP indices, at each level. The first index in a GEP 2335be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // indexes into the array implied by the pointer operand; the rest of 2345be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // the indices index into the element or field type selected by the 2355be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // preceding index. 2365be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman for (;;) { 2375be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman APInt ElSize = APInt(SE.getTypeSizeInBits(Ty), 2385be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman ElTy->isSized() ? SE.TD->getTypeAllocSize(ElTy) : 0); 2395be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman std::vector<SCEVHandle> NewOps; 2405be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman std::vector<SCEVHandle> ScaledOps; 2415be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman for (unsigned i = 0, e = Ops.size(); i != e; ++i) { 242453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // Split AddRecs up into parts as either of the parts may be usable 243453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // without the other. 244453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Ops[i])) 245453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (!A->getStart()->isZero()) { 246453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman SCEVHandle Start = A->getStart(); 247453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman Ops.push_back(SE.getAddRecExpr(SE.getIntegerSCEV(0, A->getType()), 248453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman A->getStepRecurrence(SE), 249453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman A->getLoop())); 250453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman Ops[i] = Start; 251453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman ++e; 252453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 253453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // If the scale size is not 0, attempt to factor out a scale. 2545be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (ElSize != 0) { 255453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman SCEVHandle Op = Ops[i]; 256453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (FactorOutConstant(Op, ElSize, SE)) { 257453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman ScaledOps.push_back(Op); // Op now has ElSize factored out. 2585be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman continue; 2595be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 2605be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 261453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // If the operand was not divisible, add it to the list of operands 262453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // we'll scan next iteration. 2635be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman NewOps.push_back(Ops[i]); 2645be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 2655be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Ops = NewOps; 2665be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman AnyNonZeroIndices |= !ScaledOps.empty(); 2675be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Value *Scaled = ScaledOps.empty() ? 2685be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Constant::getNullValue(Ty) : 2695be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman expandCodeFor(SE.getAddExpr(ScaledOps), Ty); 2705be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman GepIndices.push_back(Scaled); 2715be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 2725be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // Collect struct field index operands. 2735be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (!Ops.empty()) 2745be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman while (const StructType *STy = dyn_cast<StructType>(ElTy)) { 2755be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (const SCEVConstant *C = dyn_cast<SCEVConstant>(Ops[0])) 2765be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (SE.getTypeSizeInBits(C->getType()) <= 64) { 2775be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman const StructLayout &SL = *SE.TD->getStructLayout(STy); 2785be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman uint64_t FullOffset = C->getValue()->getZExtValue(); 2795be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (FullOffset < SL.getSizeInBytes()) { 2805be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman unsigned ElIdx = SL.getElementContainingOffset(FullOffset); 2815be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman GepIndices.push_back(ConstantInt::get(Type::Int32Ty, ElIdx)); 2825be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman ElTy = STy->getTypeAtIndex(ElIdx); 2835be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Ops[0] = 2845be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman SE.getConstant(ConstantInt::get(Ty, 2855be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman FullOffset - 2865be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman SL.getElementOffset(ElIdx))); 2875be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman AnyNonZeroIndices = true; 2885be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman continue; 2895be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 2905be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 2915be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman break; 2925be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 2935be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 2945be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (const ArrayType *ATy = dyn_cast<ArrayType>(ElTy)) { 2955be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman ElTy = ATy->getElementType(); 2965be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman continue; 2975be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 2985be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman break; 2995be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 3005be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 3015be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // If none of the operands were convertable to proper GEP indices, cast 3025be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // the base to i8* and do an ugly getelementptr with that. It's still 3035be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // better than ptrtoint+arithmetic+inttoptr at least. 3045be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (!AnyNonZeroIndices) { 3055be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman V = InsertNoopCastOfTo(V, 3065be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Type::Int8Ty->getPointerTo(PTy->getAddressSpace())); 3075be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Value *Idx = expand(SE.getAddExpr(Ops)); 3085be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Idx = InsertNoopCastOfTo(Idx, Ty); 3095be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 3105be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // Fold a GEP with constant operands. 3115be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (Constant *CLHS = dyn_cast<Constant>(V)) 3125be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (Constant *CRHS = dyn_cast<Constant>(Idx)) 313278b49af8a08f6ab6c486a3cfc7a9c1c1acd2b23Dan Gohman return ConstantExpr::getGetElementPtr(CLHS, &CRHS, 1); 3145be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 3155be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // Do a quick scan to see if we have this GEP nearby. If so, reuse it. 3165be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman unsigned ScanLimit = 6; 3175be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman BasicBlock::iterator BlockBegin = InsertPt->getParent()->begin(); 3185be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (InsertPt != BlockBegin) { 3195be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // Scanning starts from the last instruction before InsertPt. 3205be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman BasicBlock::iterator IP = InsertPt; 3215be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman --IP; 3225be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman for (; ScanLimit; --IP, --ScanLimit) { 3235be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (IP->getOpcode() == Instruction::GetElementPtr && 3245be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman IP->getOperand(0) == V && IP->getOperand(1) == Idx) 3255be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman return IP; 3265be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (IP == BlockBegin) break; 3275be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 3285be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 3295be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 3305be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Value *GEP = GetElementPtrInst::Create(V, Idx, "scevgep", InsertPt); 3315be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman InsertedValues.insert(GEP); 3325be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman return GEP; 3335be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 3345be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 3355be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman // Insert a pretty getelementptr. 3365be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Value *GEP = GetElementPtrInst::Create(V, 3375be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman GepIndices.begin(), 3385be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman GepIndices.end(), 3395be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman "scevgep", InsertPt); 3405be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Ops.push_back(SE.getUnknown(GEP)); 3415be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman InsertedValues.insert(GEP); 3425be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman return expand(SE.getAddExpr(Ops)); 3435be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman} 3445be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 345890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitAddExpr(const SCEVAddExpr *S) { 346af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 347e24fa64d52330626553298f56ba5aa702624c282Dan Gohman Value *V = expand(S->getOperand(S->getNumOperands()-1)); 3485be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 349453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // Turn things like ptrtoint+arithmetic+inttoptr into GEP. See the 350453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // comments on expandAddToGEP for details. 3515be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (SE.TD) 352453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (const PointerType *PTy = dyn_cast<PointerType>(V->getType())) { 353453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman const std::vector<SCEVHandle> &Ops = S->getOperands(); 354fb5a3419f351056e0f599699d276bcab412d2cceDan Gohman return expandAddToGEP(&Ops[0], &Ops[Ops.size() - 1], 355453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman PTy, Ty, V); 356453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 3575be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 358af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman V = InsertNoopCastOfTo(V, Ty); 359e24fa64d52330626553298f56ba5aa702624c282Dan Gohman 360e24fa64d52330626553298f56ba5aa702624c282Dan Gohman // Emit a bunch of add instructions 3612d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman for (int i = S->getNumOperands()-2; i >= 0; --i) { 3622d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman Value *W = expand(S->getOperand(i)); 363af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman W = InsertNoopCastOfTo(W, Ty); 3642d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman V = InsertBinop(Instruction::Add, V, W, InsertPt); 3652d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman } 366e24fa64d52330626553298f56ba5aa702624c282Dan Gohman return V; 367e24fa64d52330626553298f56ba5aa702624c282Dan Gohman} 3685be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman 369890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitMulExpr(const SCEVMulExpr *S) { 370af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 37136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman int FirstOp = 0; // Set if we should emit a subtract. 372890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getOperand(0))) 37336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman if (SC->getValue()->isAllOnesValue()) 37436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman FirstOp = 1; 37536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 37636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman int i = S->getNumOperands()-2; 377d19534add90a2a894af61523b830887097bb780bDan Gohman Value *V = expand(S->getOperand(i+1)); 378af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman V = InsertNoopCastOfTo(V, Ty); 37936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 38036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // Emit a bunch of multiply instructions 3812d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman for (; i >= FirstOp; --i) { 3822d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman Value *W = expand(S->getOperand(i)); 383af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman W = InsertNoopCastOfTo(W, Ty); 3842d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman V = InsertBinop(Instruction::Mul, V, W, InsertPt); 3852d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman } 3862d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman 38736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // -1 * ... ---> 0 - ... 38836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman if (FirstOp == 1) 3892d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman V = InsertBinop(Instruction::Sub, Constant::getNullValue(Ty), V, InsertPt); 39036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman return V; 39136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman} 39236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 393890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitUDivExpr(const SCEVUDivExpr *S) { 394af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 3952d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman 3966177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky Value *LHS = expand(S->getLHS()); 397af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman LHS = InsertNoopCastOfTo(LHS, Ty); 398890f92b744fb074465bc2b7006ee753a181f62a4Dan Gohman if (const SCEVConstant *SC = dyn_cast<SCEVConstant>(S->getRHS())) { 3996177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky const APInt &RHS = SC->getValue()->getValue(); 4006177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky if (RHS.isPowerOf2()) 4016177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky return InsertBinop(Instruction::LShr, LHS, 4022d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman ConstantInt::get(Ty, RHS.logBase2()), 4036177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky InsertPt); 4046177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky } 4056177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky 4066177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky Value *RHS = expand(S->getRHS()); 407af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman RHS = InsertNoopCastOfTo(RHS, Ty); 4086177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky return InsertBinop(Instruction::UDiv, LHS, RHS, InsertPt); 4096177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky} 4106177fd4fcee4d82692c47e33754ffe285c38cc69Nick Lewycky 411453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// Move parts of Base into Rest to leave Base with the minimal 412453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// expression that provides a pointer operand suitable for a 413453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman/// GEP expansion. 414453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohmanstatic void ExposePointerBase(SCEVHandle &Base, SCEVHandle &Rest, 415453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman ScalarEvolution &SE) { 416453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman while (const SCEVAddRecExpr *A = dyn_cast<SCEVAddRecExpr>(Base)) { 417453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman Base = A->getStart(); 418453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman Rest = SE.getAddExpr(Rest, 419453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman SE.getAddRecExpr(SE.getIntegerSCEV(0, A->getType()), 420453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman A->getStepRecurrence(SE), 421453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman A->getLoop())); 422453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 423453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (const SCEVAddExpr *A = dyn_cast<SCEVAddExpr>(Base)) { 424453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman Base = A->getOperand(A->getNumOperands()-1); 425453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman std::vector<SCEVHandle> NewAddOps(A->op_begin(), A->op_end()); 426453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman NewAddOps.back() = Rest; 427453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman Rest = SE.getAddExpr(NewAddOps); 428453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman ExposePointerBase(Base, Rest, SE); 429453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 430453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman} 431453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman 432890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitAddRecExpr(const SCEVAddRecExpr *S) { 433af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 43436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman const Loop *L = S->getLoop(); 43536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 43636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // {X,+,F} --> X + {0,+,F} 437cfeb6a450632f2a6cd05302633c8c2b8c90cfdfdDan Gohman if (!S->getStart()->isZero()) { 4385be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman std::vector<SCEVHandle> NewOps(S->getOperands()); 439246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman NewOps[0] = SE.getIntegerSCEV(0, Ty); 440453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman SCEVHandle Rest = SE.getAddRecExpr(NewOps, L); 441453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman 442453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // Turn things like ptrtoint+arithmetic+inttoptr into GEP. See the 443453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // comments on expandAddToGEP for details. 444453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (SE.TD) { 445453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman SCEVHandle Base = S->getStart(); 446453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman SCEVHandle RestArray[1] = Rest; 447453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // Dig into the expression to find the pointer base for a GEP. 448453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman ExposePointerBase(Base, RestArray[0], SE); 449453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman // If we found a pointer, expand the AddRec with a GEP. 450453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman if (const PointerType *PTy = dyn_cast<PointerType>(Base->getType())) { 451f876ad0a70c5c3bb402de2766237410f041700e6Dan Gohman // Make sure the Base isn't something exotic, such as a multiplied 452f876ad0a70c5c3bb402de2766237410f041700e6Dan Gohman // or divided pointer value. In those cases, the result type isn't 453f876ad0a70c5c3bb402de2766237410f041700e6Dan Gohman // actually a pointer type. 454f876ad0a70c5c3bb402de2766237410f041700e6Dan Gohman if (!isa<SCEVMulExpr>(Base) && !isa<SCEVUDivExpr>(Base)) { 455f876ad0a70c5c3bb402de2766237410f041700e6Dan Gohman Value *StartV = expand(Base); 456f876ad0a70c5c3bb402de2766237410f041700e6Dan Gohman assert(StartV->getType() == PTy && "Pointer type mismatch for GEP!"); 457f876ad0a70c5c3bb402de2766237410f041700e6Dan Gohman return expandAddToGEP(RestArray, RestArray+1, PTy, Ty, StartV); 458f876ad0a70c5c3bb402de2766237410f041700e6Dan Gohman } 459453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 460453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman } 461453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman 462453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman Value *RestV = expand(Rest); 463453aa4fbf1083cc7f646a0ac21e2bcc384a91ae9Dan Gohman return expand(SE.getAddExpr(S->getStart(), SE.getUnknown(RestV))); 46436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman } 46536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 46636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // {0,+,1} --> Insert a canonical induction variable into the loop! 46717f1972c770dc18f5c7c3c95776b4d62ae9e121dDan Gohman if (S->isAffine() && 468246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman S->getOperand(1) == SE.getIntegerSCEV(1, Ty)) { 46936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // Create and insert the PHI node for the induction variable in the 47036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // specified loop. 47136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman BasicBlock *Header = L->getHeader(); 472051a950000e21935165db56695e35bade668193bGabor Greif PHINode *PN = PHINode::Create(Ty, "indvar", Header->begin()); 473cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(PN); 47436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman PN->addIncoming(Constant::getNullValue(Ty), L->getLoopPreheader()); 47536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 47636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman pred_iterator HPI = pred_begin(Header); 47736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman assert(HPI != pred_end(Header) && "Loop with zero preds???"); 47836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman if (!L->contains(*HPI)) ++HPI; 47936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman assert(HPI != pred_end(Header) && L->contains(*HPI) && 48036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman "No backedge in loop?"); 48136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 48236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // Insert a unit add instruction right before the terminator corresponding 48336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // to the back-edge. 48424d6da5fedcf39891f7d8c5b031c01324b3db545Reid Spencer Constant *One = ConstantInt::get(Ty, 1); 4857cbd8a3e92221437048b484d5ef9c0a22d0f8c58Gabor Greif Instruction *Add = BinaryOperator::CreateAdd(PN, One, "indvar.next", 48636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman (*HPI)->getTerminator()); 487cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(Add); 48836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 48936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman pred_iterator PI = pred_begin(Header); 49036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman if (*PI == L->getLoopPreheader()) 49136f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman ++PI; 49236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman PN->addIncoming(Add, *PI); 49336f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman return PN; 49436f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman } 49536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 49636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // Get the canonical induction variable I for this loop. 49736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman Value *I = getOrInsertCanonicalInductionVariable(L, Ty); 49836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 499df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // If this is a simple linear addrec, emit it now as a special case. 50017f1972c770dc18f5c7c3c95776b4d62ae9e121dDan Gohman if (S->isAffine()) { // {0,+,F} --> i*F 501d19534add90a2a894af61523b830887097bb780bDan Gohman Value *F = expand(S->getOperand(1)); 502af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman F = InsertNoopCastOfTo(F, Ty); 503df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner 504df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // IF the step is by one, just return the inserted IV. 5056b6b6ef1677fa71b1072c2911b4c1f9524a558c9Zhou Sheng if (ConstantInt *CI = dyn_cast<ConstantInt>(F)) 5064d050d73210d15d8a86ee5967c417ddb5bee4543Reid Spencer if (CI->getValue() == 1) 507df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner return I; 508df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner 509df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // If the insert point is directly inside of the loop, emit the multiply at 510df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // the insert point. Otherwise, L is a loop that is a parent of the insert 511df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // point loop. If we can, move the multiply to the outer most loop that it 512df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // is safe to be in. 5136cdc727f2d7f68734526ef078f4632798ad40791Dan Gohman BasicBlock::iterator MulInsertPt = getInsertionPoint(); 5145be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman Loop *InsertPtLoop = SE.LI->getLoopFor(MulInsertPt->getParent()); 515df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner if (InsertPtLoop != L && InsertPtLoop && 516df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner L->contains(InsertPtLoop->getHeader())) { 5175d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz do { 518df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner // If we cannot hoist the multiply out of this loop, don't. 519df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner if (!InsertPtLoop->isLoopInvariant(F)) break; 520df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner 5215d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz BasicBlock *InsertPtLoopPH = InsertPtLoop->getLoopPreheader(); 5225d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz 5235d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz // If this loop hasn't got a preheader, we aren't able to hoist the 5245d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz // multiply. 5255d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz if (!InsertPtLoopPH) 5265d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz break; 5275d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz 5285d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz // Otherwise, move the insert point to the preheader. 5295d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz MulInsertPt = InsertPtLoopPH->getTerminator(); 530df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner InsertPtLoop = InsertPtLoop->getParentLoop(); 5315d2bc857ec1ae11ec2ea85e596f3712d02fd2c2bWojciech Matyjewicz } while (InsertPtLoop != L); 532df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner } 533df14a04b5ccbbe6a46c2ccb93e27b12a36ff163eChris Lattner 5347fec90ebf4ebe7aa73a6dd7d275c255587c041adChris Lattner return InsertBinop(Instruction::Mul, I, F, MulInsertPt); 53536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman } 53636f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 53736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // If this is a chain of recurrences, turn it into a closed form, using the 53836f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // folders, then expandCodeFor the closed form. This allows the folders to 53936f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // simplify the expression without having to build a bunch of special code 54036f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman // into this folder. 541246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle IH = SE.getUnknown(I); // Get I as a "symbolic" SCEV. 54236f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 543246b2564d3bbbafe06ebf6a67745cd24141b5cb4Dan Gohman SCEVHandle V = S->evaluateAtIteration(IH, SE); 544e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling //cerr << "Evaluated: " << *this << "\n to: " << *V << "\n"; 54536f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman 546d19534add90a2a894af61523b830887097bb780bDan Gohman return expand(V); 54736f891bdf6cf38fcc655a0930ca18664e18518d4Nate Begeman} 54896fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov 549890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitTruncateExpr(const SCEVTruncateExpr *S) { 550af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 55111f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman Value *V = expand(S->getOperand()); 552af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman V = InsertNoopCastOfTo(V, SE.getEffectiveSCEVType(V->getType())); 553cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *I = new TruncInst(V, Ty, "tmp.", InsertPt); 554cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(I); 555cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman return I; 55611f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman} 55711f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman 558890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitZeroExtendExpr(const SCEVZeroExtendExpr *S) { 559af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 56011f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman Value *V = expand(S->getOperand()); 561af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman V = InsertNoopCastOfTo(V, SE.getEffectiveSCEVType(V->getType())); 562cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *I = new ZExtInst(V, Ty, "tmp.", InsertPt); 563cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(I); 564cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman return I; 56511f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman} 56611f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman 567890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitSignExtendExpr(const SCEVSignExtendExpr *S) { 568af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 56911f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman Value *V = expand(S->getOperand()); 570af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman V = InsertNoopCastOfTo(V, SE.getEffectiveSCEVType(V->getType())); 571cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *I = new SExtInst(V, Ty, "tmp.", InsertPt); 572cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(I); 573cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman return I; 57411f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman} 57511f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman 576890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitSMaxExpr(const SCEVSMaxExpr *S) { 577af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 578c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky Value *LHS = expand(S->getOperand(0)); 579af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman LHS = InsertNoopCastOfTo(LHS, Ty); 580c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky for (unsigned i = 1; i < S->getNumOperands(); ++i) { 581c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky Value *RHS = expand(S->getOperand(i)); 582af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman RHS = InsertNoopCastOfTo(RHS, Ty); 583cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *ICmp = 584cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman new ICmpInst(ICmpInst::ICMP_SGT, LHS, RHS, "tmp", InsertPt); 585cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(ICmp); 586cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *Sel = SelectInst::Create(ICmp, LHS, RHS, "smax", InsertPt); 587cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(Sel); 588cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman LHS = Sel; 589c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky } 590c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky return LHS; 591c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky} 592c54c561c9f7270c055dd7ba75a3a003b771a42d9Nick Lewycky 593890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::visitUMaxExpr(const SCEVUMaxExpr *S) { 594af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman const Type *Ty = SE.getEffectiveSCEVType(S->getType()); 5953e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky Value *LHS = expand(S->getOperand(0)); 596af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman LHS = InsertNoopCastOfTo(LHS, Ty); 5973e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky for (unsigned i = 1; i < S->getNumOperands(); ++i) { 5983e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky Value *RHS = expand(S->getOperand(i)); 599af79fb5f47b0088c6a8973a7fdbaea96973a429dDan Gohman RHS = InsertNoopCastOfTo(RHS, Ty); 600cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *ICmp = 601cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman new ICmpInst(ICmpInst::ICMP_UGT, LHS, RHS, "tmp", InsertPt); 602cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(ICmp); 603cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman Instruction *Sel = SelectInst::Create(ICmp, LHS, RHS, "umax", InsertPt); 604cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman InsertedValues.insert(Sel); 605cf5ab820227dedd77fb91d0904b6dc3694a7c196Dan Gohman LHS = Sel; 6063e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky } 6073e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky return LHS; 6083e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky} 6093e6307698084e7adfc10b739442ae29742beefd0Nick Lewycky 610752ec7da506f5d41c08bd37e195750b57550ce68Dan GohmanValue *SCEVExpander::expandCodeFor(SCEVHandle SH, const Type *Ty) { 61111f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman // Expand the code for this SCEV. 6122d1be87ee40a4a0241d94448173879d9df2bc5b3Dan Gohman Value *V = expand(SH); 6135be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman if (Ty) { 6145be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman assert(SE.getTypeSizeInBits(Ty) == SE.getTypeSizeInBits(SH->getType()) && 6155be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman "non-trivial casts should be done with the SCEVs directly!"); 6165be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman V = InsertNoopCastOfTo(V, Ty); 6175be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman } 6185be18e84766fb495b0bde3c8244c1df459a18683Dan Gohman return V; 61911f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman} 62011f6d3b478c4fa09d126833c57fbac1d795ead31Dan Gohman 621890f92b744fb074465bc2b7006ee753a181f62a4Dan GohmanValue *SCEVExpander::expand(const SCEV *S) { 62296fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov // Check to see if we already expanded this. 6233790fb0c036acaa4db50aff83dd8b3bf51f8af6aTorok Edwin std::map<SCEVHandle, AssertingVH<Value> >::iterator I = 6243790fb0c036acaa4db50aff83dd8b3bf51f8af6aTorok Edwin InsertedExpressions.find(S); 62596fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov if (I != InsertedExpressions.end()) 62696fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov return I->second; 62796fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov 62896fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov Value *V = visit(S); 62996fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov InsertedExpressions[S] = V; 63096fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov return V; 63196fea337d27357e9b62abbf3d2d5ce29f1c8e870Anton Korobeynikov} 632