1d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner//===-- IPConstantPropagation.cpp - Propagate constants through calls -----===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner// The LLVM Compiler Infrastructure 4d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner//===----------------------------------------------------------------------===// 9d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner// 10d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner// This pass implements an _extremely_ simple interprocedural constant 11d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner// propagation pass. It could certainly be improved in many different ways, 12d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner// like using a worklist. This pass makes arguments dead, but does not remove 13d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner// them. The existing dead argument elimination pass should be run after this 14d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner// to clean up the mess. 15d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner// 16d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner//===----------------------------------------------------------------------===// 17d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner 1886453c52ba02e743d29c08456e51006500041456Chris Lattner#define DEBUG_TYPE "ipconstprop" 19d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner#include "llvm/Transforms/IPO.h" 20a990d94330141404158a2ae6ba25661be4468b25Chris Lattner#include "llvm/Constants.h" 21a990d94330141404158a2ae6ba25661be4468b25Chris Lattner#include "llvm/Instructions.h" 22d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner#include "llvm/Module.h" 23d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner#include "llvm/Pass.h" 248b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman#include "llvm/Analysis/ValueTracking.h" 25d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner#include "llvm/Support/CallSite.h" 26551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/Statistic.h" 277db30ba70111bd082d854e00f0b854c8d91eed76Devang Patel#include "llvm/ADT/SmallVector.h" 281e2385b941242f2f96398dc62767420622856149Chris Lattnerusing namespace llvm; 29d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 3086453c52ba02e743d29c08456e51006500041456Chris LattnerSTATISTIC(NumArgumentsProped, "Number of args turned into constants"); 3186453c52ba02e743d29c08456e51006500041456Chris LattnerSTATISTIC(NumReturnValProped, "Number of return values turned into constants"); 32d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner 3386453c52ba02e743d29c08456e51006500041456Chris Lattnernamespace { 34d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner /// IPCP - The interprocedural constant propagation pass 35d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner /// 366726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky struct IPCP : public ModulePass { 37ecd94c804a563f2a86572dcf1d2e81f397e19daaNick Lewycky static char ID; // Pass identification, replacement for typeid 38081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson IPCP() : ModulePass(ID) { 39081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeIPCPPass(*PassRegistry::getPassRegistry()); 40081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 41794fd75c67a2cdc128d67342c6d88a504d186896Devang Patel 42b12914bfc0f76a7a48357162d5f4c39a1343e69bChris Lattner bool runOnModule(Module &M); 43d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner private: 44a990d94330141404158a2ae6ba25661be4468b25Chris Lattner bool PropagateConstantsIntoArguments(Function &F); 45a990d94330141404158a2ae6ba25661be4468b25Chris Lattner bool PropagateConstantReturn(Function &F); 46d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner }; 47d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner} 48d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner 49844731a7f1909f55935e3514c9e713a62d67662eDan Gohmanchar IPCP::ID = 0; 50d13db2c59cc94162d6cf0a04187d408bfef6d4a7Owen AndersonINITIALIZE_PASS(IPCP, "ipconstprop", 51ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Interprocedural constant propagation", false, false) 52844731a7f1909f55935e3514c9e713a62d67662eDan Gohman 53b12914bfc0f76a7a48357162d5f4c39a1343e69bChris LattnerModulePass *llvm::createIPConstantPropagationPass() { return new IPCP(); } 54d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner 55b12914bfc0f76a7a48357162d5f4c39a1343e69bChris Lattnerbool IPCP::runOnModule(Module &M) { 56d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner bool Changed = false; 572e8dfb8221d8fbb4d007cd1ab5e63dac0accea4bChris Lattner bool LocalChange = true; 582e8dfb8221d8fbb4d007cd1ab5e63dac0accea4bChris Lattner 592e8dfb8221d8fbb4d007cd1ab5e63dac0accea4bChris Lattner // FIXME: instead of using smart algorithms, we just iterate until we stop 602e8dfb8221d8fbb4d007cd1ab5e63dac0accea4bChris Lattner // making changes. 612e8dfb8221d8fbb4d007cd1ab5e63dac0accea4bChris Lattner while (LocalChange) { 622e8dfb8221d8fbb4d007cd1ab5e63dac0accea4bChris Lattner LocalChange = false; 632e8dfb8221d8fbb4d007cd1ab5e63dac0accea4bChris Lattner for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) 645cbf985dcbc89fba3208e7baf8b6f488b06d3ec9Reid Spencer if (!I->isDeclaration()) { 65a990d94330141404158a2ae6ba25661be4468b25Chris Lattner // Delete any klingons. 66a990d94330141404158a2ae6ba25661be4468b25Chris Lattner I->removeDeadConstantUsers(); 67bb46f52027416598a662dc1c58f48d9d56b1a65bRafael Espindola if (I->hasLocalLinkage()) 68a990d94330141404158a2ae6ba25661be4468b25Chris Lattner LocalChange |= PropagateConstantsIntoArguments(*I); 69a990d94330141404158a2ae6ba25661be4468b25Chris Lattner Changed |= PropagateConstantReturn(*I); 70a990d94330141404158a2ae6ba25661be4468b25Chris Lattner } 712e8dfb8221d8fbb4d007cd1ab5e63dac0accea4bChris Lattner Changed |= LocalChange; 722e8dfb8221d8fbb4d007cd1ab5e63dac0accea4bChris Lattner } 73d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner return Changed; 74d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner} 75d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner 76a990d94330141404158a2ae6ba25661be4468b25Chris Lattner/// PropagateConstantsIntoArguments - Look at all uses of the specified 77a990d94330141404158a2ae6ba25661be4468b25Chris Lattner/// function. If all uses are direct call sites, and all pass a particular 78a990d94330141404158a2ae6ba25661be4468b25Chris Lattner/// constant in for an argument, propagate that constant in as the argument. 79d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner/// 80a990d94330141404158a2ae6ba25661be4468b25Chris Lattnerbool IPCP::PropagateConstantsIntoArguments(Function &F) { 817f8897f22e88271cfa114998a4d6088e7c8e8e11Chris Lattner if (F.arg_empty() || F.use_empty()) return false; // No arguments? Early exit. 82d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner 834af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner // For each argument, keep track of its constant value and whether it is a 844af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner // constant or not. The bool is driven to true when found to be non-constant. 854af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner SmallVector<std::pair<Constant*, bool>, 16> ArgumentConstants; 86e4d5c441e04bdc00ccf1804744af670655123b07Chris Lattner ArgumentConstants.resize(F.arg_size()); 87d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner 88d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner unsigned NumNonconstant = 0; 894af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner for (Value::use_iterator UI = F.use_begin(), E = F.use_end(); UI != E; ++UI) { 9065b9212d344d97f7305f61048c1c87bd5ffa0c32Gabor Greif User *U = *UI; 91b2710041fbed34ae888a6fed4172aea92bced1b5Chris Lattner // Ignore blockaddress uses. 9265b9212d344d97f7305f61048c1c87bd5ffa0c32Gabor Greif if (isa<BlockAddress>(U)) continue; 93b2710041fbed34ae888a6fed4172aea92bced1b5Chris Lattner 944af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner // Used by a non-instruction, or not the callee of a function, do not 954af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner // transform. 9665b9212d344d97f7305f61048c1c87bd5ffa0c32Gabor Greif if (!isa<CallInst>(U) && !isa<InvokeInst>(U)) 974af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner return false; 984af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner 997d3056b16038a6a09c452c0dfcc3c8f4e421506aGabor Greif CallSite CS(cast<Instruction>(U)); 100edc4d69917df7dc34543adf719d5c93249fd5e27Gabor Greif if (!CS.isCallee(UI)) 101edc4d69917df7dc34543adf719d5c93249fd5e27Gabor Greif return false; 1024af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner 1034af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner // Check out all of the potentially constant arguments. Note that we don't 1044af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner // inspect varargs here. 1054af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner CallSite::arg_iterator AI = CS.arg_begin(); 1064af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner Function::arg_iterator Arg = F.arg_begin(); 1074af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner for (unsigned i = 0, e = ArgumentConstants.size(); i != e; 1084af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner ++i, ++AI, ++Arg) { 1094af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner 1104af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner // If this argument is known non-constant, ignore it. 1114af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner if (ArgumentConstants[i].second) 1124af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner continue; 1134af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner 1144af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner Constant *C = dyn_cast<Constant>(*AI); 1154af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner if (C && ArgumentConstants[i].first == 0) { 1164af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner ArgumentConstants[i].first = C; // First constant seen. 1174af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner } else if (C && ArgumentConstants[i].first == C) { 1184af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner // Still the constant value we think it is. 1194af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner } else if (*AI == &*Arg) { 1204af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner // Ignore recursive calls passing argument down. 1214af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner } else { 1224af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner // Argument became non-constant. If all arguments are non-constant now, 1234af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner // give up on this function. 1244af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner if (++NumNonconstant == ArgumentConstants.size()) 1254af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner return false; 1264af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner ArgumentConstants[i].second = true; 127d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner } 128d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner } 1294af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner } 130d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner 131d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner // If we got to this point, there is a constant argument! 132d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner assert(NumNonconstant != ArgumentConstants.size()); 1332e8dfb8221d8fbb4d007cd1ab5e63dac0accea4bChris Lattner bool MadeChange = false; 1344af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner Function::arg_iterator AI = F.arg_begin(); 1354af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner for (unsigned i = 0, e = ArgumentConstants.size(); i != e; ++i, ++AI) { 1364af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner // Do we have a constant argument? 137c3384995258efcec26acf3a88715dc99cd871c3eTorok Edwin if (ArgumentConstants[i].second || AI->use_empty() || 138c3384995258efcec26acf3a88715dc99cd871c3eTorok Edwin (AI->hasByValAttr() && !F.onlyReadsMemory())) 1394af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner continue; 1404af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner 1414af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner Value *V = ArgumentConstants[i].first; 1429e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson if (V == 0) V = UndefValue::get(AI->getType()); 1434af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner AI->replaceAllUsesWith(V); 1444af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner ++NumArgumentsProped; 1454af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner MadeChange = true; 1464af6ad37898bcda9e29fe1c7abbb1b9899af3b5bChris Lattner } 1472e8dfb8221d8fbb4d007cd1ab5e63dac0accea4bChris Lattner return MadeChange; 148d358e6fed51113b216756ea08fa361bb82022df2Chris Lattner} 149d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 150a990d94330141404158a2ae6ba25661be4468b25Chris Lattner 1518b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman// Check to see if this function returns one or more constants. If so, replace 1528b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman// all callers that use those return values with the constant value. This will 1538b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman// leave in the actual return values and instructions, but deadargelim will 1548b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman// clean that up. 155c2afe89019790adb2c590397960d69b8f1d9a537Matthijs Kooijman// 156c2afe89019790adb2c590397960d69b8f1d9a537Matthijs Kooijman// Additionally if a function always returns one of its arguments directly, 157c2afe89019790adb2c590397960d69b8f1d9a537Matthijs Kooijman// callers will be updated to use the value they pass in directly instead of 158c2afe89019790adb2c590397960d69b8f1d9a537Matthijs Kooijman// using the return value. 159a990d94330141404158a2ae6ba25661be4468b25Chris Lattnerbool IPCP::PropagateConstantReturn(Function &F) { 160ae3d802953b5209e7e9530cd5b5d4e457a6974dcNick Lewycky if (F.getReturnType()->isVoidTy()) 161a990d94330141404158a2ae6ba25661be4468b25Chris Lattner return false; // No return value. 162a990d94330141404158a2ae6ba25661be4468b25Chris Lattner 16318d73c206e8259de61abf54d8d0f47c0e54f42aaChris Lattner // If this function could be overridden later in the link stage, we can't 16418d73c206e8259de61abf54d8d0f47c0e54f42aaChris Lattner // propagate information about its results into callers. 1655ed3b894c913b0d4f4a0f3bd47f3ea1adf6eb52eNuno Lopes if (F.mayBeOverridden()) 16618d73c206e8259de61abf54d8d0f47c0e54f42aaChris Lattner return false; 167e922c0201916e0b980ab3cfe91e1413e68d55647Owen Anderson 168a990d94330141404158a2ae6ba25661be4468b25Chris Lattner // Check to see if this function returns a constant. 1697db30ba70111bd082d854e00f0b854c8d91eed76Devang Patel SmallVector<Value *,4> RetVals; 170db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner StructType *STy = dyn_cast<StructType>(F.getReturnType()); 1717db30ba70111bd082d854e00f0b854c8d91eed76Devang Patel if (STy) 1728b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman for (unsigned i = 0, e = STy->getNumElements(); i < e; ++i) 1739e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson RetVals.push_back(UndefValue::get(STy->getElementType(i))); 1747db30ba70111bd082d854e00f0b854c8d91eed76Devang Patel else 1759e9a0d5fc26878e51a58a8b57900fcbf952c2691Owen Anderson RetVals.push_back(UndefValue::get(F.getReturnType())); 1767db30ba70111bd082d854e00f0b854c8d91eed76Devang Patel 1778b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman unsigned NumNonConstant = 0; 178a990d94330141404158a2ae6ba25661be4468b25Chris Lattner for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) 17907e6e56f57e8781a8d7bc601cc9034a3741d84c2Anton Korobeynikov if (ReturnInst *RI = dyn_cast<ReturnInst>(BB->getTerminator())) { 180e9625c6c88477382d7b4db6c16108ab2db2b1326Chris Lattner for (unsigned i = 0, e = RetVals.size(); i != e; ++i) { 1818b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman // Already found conflicting return values? 182e9625c6c88477382d7b4db6c16108ab2db2b1326Chris Lattner Value *RV = RetVals[i]; 1838b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman if (!RV) 1848b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman continue; 1858b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman 1868b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman // Find the returned value 1878b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman Value *V; 188792e1e92c78be7a8610405d05a5e16dae6265dddDan Gohman if (!STy) 1893e2f74e6d6dbc07563ba8ee9ffd2a230514929fbJay Foad V = RI->getOperand(0); 1908b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman else 191ae3d802953b5209e7e9530cd5b5d4e457a6974dcNick Lewycky V = FindInsertedValue(RI->getOperand(0), i); 1928b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman 1938b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman if (V) { 1948b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman // Ignore undefs, we can change them into anything 1958b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman if (isa<UndefValue>(V)) 1968b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman continue; 1978b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman 198c2afe89019790adb2c590397960d69b8f1d9a537Matthijs Kooijman // Try to see if all the rets return the same constant or argument. 199c2afe89019790adb2c590397960d69b8f1d9a537Matthijs Kooijman if (isa<Constant>(V) || isa<Argument>(V)) { 2008b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman if (isa<UndefValue>(RV)) { 2018b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman // No value found yet? Try the current one. 2028b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman RetVals[i] = V; 2038b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman continue; 2048b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman } 2058b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman // Returning the same value? Good. 2068b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman if (RV == V) 2078b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman continue; 2088b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman } 2098b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman } 2108b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman // Different or no known return value? Don't propagate this return 2118b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman // value. 2128b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman RetVals[i] = 0; 2138b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman // All values non constant? Stop looking. 2148b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman if (++NumNonConstant == RetVals.size()) 2158b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman return false; 216a990d94330141404158a2ae6ba25661be4468b25Chris Lattner } 21707e6e56f57e8781a8d7bc601cc9034a3741d84c2Anton Korobeynikov } 218a990d94330141404158a2ae6ba25661be4468b25Chris Lattner 2198b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman // If we got here, the function returns at least one constant value. Loop 2208b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman // over all users, replacing any uses of the return value with the returned 2218b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman // constant. 222a990d94330141404158a2ae6ba25661be4468b25Chris Lattner bool MadeChange = false; 223e9625c6c88477382d7b4db6c16108ab2db2b1326Chris Lattner for (Value::use_iterator UI = F.use_begin(), E = F.use_end(); UI != E; ++UI) { 2247d3056b16038a6a09c452c0dfcc3c8f4e421506aGabor Greif CallSite CS(*UI); 225f0da2039d17a3e6b72fd1c0df1f889afac65cbd0Matthijs Kooijman Instruction* Call = CS.getInstruction(); 226f0da2039d17a3e6b72fd1c0df1f889afac65cbd0Matthijs Kooijman 227f0da2039d17a3e6b72fd1c0df1f889afac65cbd0Matthijs Kooijman // Not a call instruction or a call instruction that's not calling F 228f0da2039d17a3e6b72fd1c0df1f889afac65cbd0Matthijs Kooijman // directly? 229edc4d69917df7dc34543adf719d5c93249fd5e27Gabor Greif if (!Call || !CS.isCallee(UI)) 230e9625c6c88477382d7b4db6c16108ab2db2b1326Chris Lattner continue; 231e9625c6c88477382d7b4db6c16108ab2db2b1326Chris Lattner 232f0da2039d17a3e6b72fd1c0df1f889afac65cbd0Matthijs Kooijman // Call result not used? 233e9625c6c88477382d7b4db6c16108ab2db2b1326Chris Lattner if (Call->use_empty()) 234e9625c6c88477382d7b4db6c16108ab2db2b1326Chris Lattner continue; 235e9625c6c88477382d7b4db6c16108ab2db2b1326Chris Lattner 236e9625c6c88477382d7b4db6c16108ab2db2b1326Chris Lattner MadeChange = true; 237a990d94330141404158a2ae6ba25661be4468b25Chris Lattner 238e9625c6c88477382d7b4db6c16108ab2db2b1326Chris Lattner if (STy == 0) { 239c2afe89019790adb2c590397960d69b8f1d9a537Matthijs Kooijman Value* New = RetVals[0]; 240c2afe89019790adb2c590397960d69b8f1d9a537Matthijs Kooijman if (Argument *A = dyn_cast<Argument>(New)) 241c2afe89019790adb2c590397960d69b8f1d9a537Matthijs Kooijman // Was an argument returned? Then find the corresponding argument in 242f0da2039d17a3e6b72fd1c0df1f889afac65cbd0Matthijs Kooijman // the call instruction and use that. 243f0da2039d17a3e6b72fd1c0df1f889afac65cbd0Matthijs Kooijman New = CS.getArgument(A->getArgNo()); 244c2afe89019790adb2c590397960d69b8f1d9a537Matthijs Kooijman Call->replaceAllUsesWith(New); 245e9625c6c88477382d7b4db6c16108ab2db2b1326Chris Lattner continue; 246e9625c6c88477382d7b4db6c16108ab2db2b1326Chris Lattner } 247e9625c6c88477382d7b4db6c16108ab2db2b1326Chris Lattner 2488b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman for (Value::use_iterator I = Call->use_begin(), E = Call->use_end(); 2498b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman I != E;) { 2500906b1bf09769d5301e62d372b363b4cd0b5a6c7Jay Foad Instruction *Ins = cast<Instruction>(*I); 2518b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman 2528b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman // Increment now, so we can remove the use 2538b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman ++I; 2548b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman 2558b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman // Find the index of the retval to replace with 2568b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman int index = -1; 257fc74abfba5128544a750fce22fdf13eb0403e3ceDan Gohman if (ExtractValueInst *EV = dyn_cast<ExtractValueInst>(Ins)) 2588b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman if (EV->hasIndices()) 2598b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman index = *EV->idx_begin(); 2608b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman 2618b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman // If this use uses a specific return value, and we have a replacement, 2628b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman // replace it. 2638b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman if (index != -1) { 2648b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman Value *New = RetVals[index]; 2658b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman if (New) { 266c2afe89019790adb2c590397960d69b8f1d9a537Matthijs Kooijman if (Argument *A = dyn_cast<Argument>(New)) 267c2afe89019790adb2c590397960d69b8f1d9a537Matthijs Kooijman // Was an argument returned? Then find the corresponding argument in 268f0da2039d17a3e6b72fd1c0df1f889afac65cbd0Matthijs Kooijman // the call instruction and use that. 269f0da2039d17a3e6b72fd1c0df1f889afac65cbd0Matthijs Kooijman New = CS.getArgument(A->getArgNo()); 2708b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman Ins->replaceAllUsesWith(New); 2718b0fcf38ef08874af8c718520a33554d73f7bd4fMatthijs Kooijman Ins->eraseFromParent(); 2722ffa47b6bf5e98f887a45fd3a51452d4f3b67c2dChris Lattner } 273488b678a4915eae8e878f5776549a19493edecf7Devang Patel } 2747db30ba70111bd082d854e00f0b854c8d91eed76Devang Patel } 275a990d94330141404158a2ae6ba25661be4468b25Chris Lattner } 276a990d94330141404158a2ae6ba25661be4468b25Chris Lattner 277a990d94330141404158a2ae6ba25661be4468b25Chris Lattner if (MadeChange) ++NumReturnValProped; 278a990d94330141404158a2ae6ba25661be4468b25Chris Lattner return MadeChange; 279a990d94330141404158a2ae6ba25661be4468b25Chris Lattner} 280