19e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands//===- FunctionAttrs.cpp - Pass which marks functions readnone or readonly ===// 29e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands// 39e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands// The LLVM Compiler Infrastructure 49e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands// 59e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands// This file is distributed under the University of Illinois Open Source 69e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands// License. See LICENSE.TXT for details. 79e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands// 89e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands//===----------------------------------------------------------------------===// 99e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands// 109e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands// This file implements a simple interprocedural pass which walks the 119e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands// call-graph, looking for functions which do not access or only read 12b2f2279056ab9e2e80f94c20d79affc007a4de62Duncan Sands// non-local memory, and marking them readnone/readonly. In addition, 13b2f2279056ab9e2e80f94c20d79affc007a4de62Duncan Sands// it marks function arguments (of pointer type) 'nocapture' if a call 14b2f2279056ab9e2e80f94c20d79affc007a4de62Duncan Sands// to the function does not create any copies of the pointer value that 15b2f2279056ab9e2e80f94c20d79affc007a4de62Duncan Sands// outlive the call. This more or less means that the pointer is only 16b2f2279056ab9e2e80f94c20d79affc007a4de62Duncan Sands// dereferenced, and not returned from the function or stored in a global. 17b2f2279056ab9e2e80f94c20d79affc007a4de62Duncan Sands// This pass is implemented as a bottom-up traversal of the call-graph. 189e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands// 199e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands//===----------------------------------------------------------------------===// 209e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 219e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands#define DEBUG_TYPE "functionattrs" 229e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands#include "llvm/Transforms/IPO.h" 23b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky#include "llvm/ADT/SCCIterator.h" 24b4c9d9c51fcb8a4cad2336b1ad9d225f504bbc4cBenjamin Kramer#include "llvm/ADT/SetVector.h" 25338cd6ba6e36c291185541bb8e391427f57a32b1Duncan Sands#include "llvm/ADT/SmallSet.h" 269e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands#include "llvm/ADT/Statistic.h" 27d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/AliasAnalysis.h" 28d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/CallGraph.h" 293251e81d793a293b78f4914be6093b405c24fc2aChandler Carruth#include "llvm/Analysis/CallGraphSCCPass.h" 30d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/CaptureTracking.h" 310b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/GlobalVariable.h" 320b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IntrinsicInst.h" 330b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/LLVMContext.h" 349e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands#include "llvm/Support/InstIterator.h" 359e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sandsusing namespace llvm; 369e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 379e89ba31f16a960239a750a26a982b4c9dfe8949Duncan SandsSTATISTIC(NumReadNone, "Number of functions marked readnone"); 389e89ba31f16a960239a750a26a982b4c9dfe8949Duncan SandsSTATISTIC(NumReadOnly, "Number of functions marked readonly"); 399e89ba31f16a960239a750a26a982b4c9dfe8949Duncan SandsSTATISTIC(NumNoCapture, "Number of arguments marked nocapture"); 40199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick LewyckySTATISTIC(NumNoAlias, "Number of function returns marked noalias"); 419e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 429e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sandsnamespace { 436726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky struct FunctionAttrs : public CallGraphSCCPass { 449e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands static char ID; // Pass identification, replacement for typeid 453c97f7af9e75507f12a3977bced6b91c7e2ffb2aDan Gohman FunctionAttrs() : CallGraphSCCPass(ID), AA(0) { 46081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson initializeFunctionAttrsPass(*PassRegistry::getPassRegistry()); 47081c34b725980f995be9080eaec24cd3dfaaf065Owen Anderson } 489e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 499e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands // runOnSCC - Analyze the SCC, performing the transformation if possible. 502decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner bool runOnSCC(CallGraphSCC &SCC); 519e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 529e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands // AddReadAttrs - Deduce readonly/readnone attributes for the SCC. 532decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner bool AddReadAttrs(const CallGraphSCC &SCC); 549e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 559e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands // AddNoCaptureAttrs - Deduce nocapture attributes for the SCC. 562decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner bool AddNoCaptureAttrs(const CallGraphSCC &SCC); 579e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 58199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky // IsFunctionMallocLike - Does this function allocate new memory? 59199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky bool IsFunctionMallocLike(Function *F, 6098a27ce03f092ab5464e65725f7d1fa0c03652f2Chris Lattner SmallPtrSet<Function*, 8> &) const; 61199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky 62199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky // AddNoAliasAttrs - Deduce noalias attributes for the SCC. 632decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner bool AddNoAliasAttrs(const CallGraphSCC &SCC); 64199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky 659e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands virtual void getAnalysisUsage(AnalysisUsage &AU) const { 669e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands AU.setPreservesCFG(); 673c97f7af9e75507f12a3977bced6b91c7e2ffb2aDan Gohman AU.addRequired<AliasAnalysis>(); 689e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands CallGraphSCCPass::getAnalysisUsage(AU); 699e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands } 709e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 713c97f7af9e75507f12a3977bced6b91c7e2ffb2aDan Gohman private: 723c97f7af9e75507f12a3977bced6b91c7e2ffb2aDan Gohman AliasAnalysis *AA; 739e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands }; 749e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands} 759e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 769e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sandschar FunctionAttrs::ID = 0; 77ae0a7bc68303ce0c8721f0e981ae602601390e68Owen AndersonINITIALIZE_PASS_BEGIN(FunctionAttrs, "functionattrs", 78ae0a7bc68303ce0c8721f0e981ae602601390e68Owen Anderson "Deduce function attributes", false, false) 79ae0a7bc68303ce0c8721f0e981ae602601390e68Owen AndersonINITIALIZE_AG_DEPENDENCY(CallGraph) 80ae0a7bc68303ce0c8721f0e981ae602601390e68Owen AndersonINITIALIZE_PASS_END(FunctionAttrs, "functionattrs", 81ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Deduce function attributes", false, false) 829e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 839e89ba31f16a960239a750a26a982b4c9dfe8949Duncan SandsPass *llvm::createFunctionAttrsPass() { return new FunctionAttrs(); } 849e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 859e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 869e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands/// AddReadAttrs - Deduce readonly/readnone attributes for the SCC. 872decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattnerbool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) { 8898a27ce03f092ab5464e65725f7d1fa0c03652f2Chris Lattner SmallPtrSet<Function*, 8> SCCNodes; 899e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 909e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands // Fill SCCNodes with the elements of the SCC. Used for quickly 919e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands // looking up whether a given CallGraphNode is in this SCC. 922decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) 932decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner SCCNodes.insert((*I)->getFunction()); 949e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 959e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands // Check if any of the functions in the SCC read or write memory. If they 969e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands // write memory then they can't be marked readnone or readonly. 979e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands bool ReadsMemory = false; 982decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 992decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner Function *F = (*I)->getFunction(); 1009e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 1019e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands if (F == 0) 1029e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands // External node - may write memory. Just give up. 1039e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands return false; 1049e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 1056d44d64f61359c865cbf2d7f331bb9c97ce253d5Dan Gohman AliasAnalysis::ModRefBehavior MRB = AA->getModRefBehavior(F); 1066d44d64f61359c865cbf2d7f331bb9c97ce253d5Dan Gohman if (MRB == AliasAnalysis::DoesNotAccessMemory) 1079e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands // Already perfect! 1089e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands continue; 1099e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 1109e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands // Definitions with weak linkage may be overridden at linktime with 1119e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands // something that writes memory, so treat them like declarations. 1129e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands if (F->isDeclaration() || F->mayBeOverridden()) { 1136d44d64f61359c865cbf2d7f331bb9c97ce253d5Dan Gohman if (!AliasAnalysis::onlyReadsMemory(MRB)) 1149e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands // May write memory. Just give up. 1159e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands return false; 1169e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 1179e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands ReadsMemory = true; 1189e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands continue; 1199e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands } 1209e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 1219e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands // Scan the function body for instructions that may read or write memory. 1229e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) { 1239e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands Instruction *I = &*II; 1249e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 1259e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands // Some instructions can be ignored even if they read or write memory. 1269e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands // Detect these now, skipping to the next instruction if one is found. 1277d3056b16038a6a09c452c0dfcc3c8f4e421506aGabor Greif CallSite CS(cast<Value>(I)); 1283c97f7af9e75507f12a3977bced6b91c7e2ffb2aDan Gohman if (CS) { 1299e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands // Ignore calls to functions in the same SCC. 1303c97f7af9e75507f12a3977bced6b91c7e2ffb2aDan Gohman if (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction())) 1313c97f7af9e75507f12a3977bced6b91c7e2ffb2aDan Gohman continue; 13242c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman AliasAnalysis::ModRefBehavior MRB = AA->getModRefBehavior(CS); 13342c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman // If the call doesn't access arbitrary memory, we may be able to 13442c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman // figure out something. 135432d08cbdb9ceaa333f1d6eab4f8b542fdddf9dbDan Gohman if (AliasAnalysis::onlyAccessesArgPointees(MRB)) { 136432d08cbdb9ceaa333f1d6eab4f8b542fdddf9dbDan Gohman // If the call does access argument pointees, check each argument. 13768a6056dafd4913ce42606353ab1ff7208215ff2Dan Gohman if (AliasAnalysis::doesAccessArgPointees(MRB)) 13842c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman // Check whether all pointer arguments point to local memory, and 13942c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman // ignore calls that only access local memory. 14042c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 14142c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman CI != CE; ++CI) { 14242c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman Value *Arg = *CI; 14342c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman if (Arg->getType()->isPointerTy()) { 14442c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman AliasAnalysis::Location Loc(Arg, 14542c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman AliasAnalysis::UnknownSize, 14642c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman I->getMetadata(LLVMContext::MD_tbaa)); 14742c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman if (!AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) { 14842c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman if (MRB & AliasAnalysis::Mod) 14942c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman // Writes non-local memory. Give up. 15042c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman return false; 15142c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman if (MRB & AliasAnalysis::Ref) 15242c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman // Ok, it reads non-local memory. 15342c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman ReadsMemory = true; 15442c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman } 15540b6a19daa0efa5131a56aa15cc8694d3cf6171eDan Gohman } 15640b6a19daa0efa5131a56aa15cc8694d3cf6171eDan Gohman } 15740b6a19daa0efa5131a56aa15cc8694d3cf6171eDan Gohman continue; 1583c97f7af9e75507f12a3977bced6b91c7e2ffb2aDan Gohman } 15942c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman // The call could access any memory. If that includes writes, give up. 16042c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman if (MRB & AliasAnalysis::Mod) 16142c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman return false; 16242c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman // If it reads, note it. 16342c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman if (MRB & AliasAnalysis::Ref) 16442c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman ReadsMemory = true; 16542c31a70735e55bf82e66a9315c97d1821c9a798Dan Gohman continue; 1669e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 1672199dfb0e6b98fdce0a3c863eb84d466d426b968Eli Friedman // Ignore non-volatile loads from local memory. (Atomic is okay here.) 1682199dfb0e6b98fdce0a3c863eb84d466d426b968Eli Friedman if (!LI->isVolatile()) { 1696d8eb156e6be727570b300bac7712f745a318c7dDan Gohman AliasAnalysis::Location Loc = AA->getLocation(LI); 170ea8900f5df76e11efb9464157af160f5fa41e9c0Dan Gohman if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) 171ea8900f5df76e11efb9464157af160f5fa41e9c0Dan Gohman continue; 172ea8900f5df76e11efb9464157af160f5fa41e9c0Dan Gohman } 1739e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 1742199dfb0e6b98fdce0a3c863eb84d466d426b968Eli Friedman // Ignore non-volatile stores to local memory. (Atomic is okay here.) 1752199dfb0e6b98fdce0a3c863eb84d466d426b968Eli Friedman if (!SI->isVolatile()) { 1766d8eb156e6be727570b300bac7712f745a318c7dDan Gohman AliasAnalysis::Location Loc = AA->getLocation(SI); 177ea8900f5df76e11efb9464157af160f5fa41e9c0Dan Gohman if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) 178ea8900f5df76e11efb9464157af160f5fa41e9c0Dan Gohman continue; 179ea8900f5df76e11efb9464157af160f5fa41e9c0Dan Gohman } 1804cf0dcfb44d9d308f2df48e2878c91297395179cDan Gohman } else if (VAArgInst *VI = dyn_cast<VAArgInst>(I)) { 1814cf0dcfb44d9d308f2df48e2878c91297395179cDan Gohman // Ignore vaargs on local memory. 1826d8eb156e6be727570b300bac7712f745a318c7dDan Gohman AliasAnalysis::Location Loc = AA->getLocation(VI); 1834cf0dcfb44d9d308f2df48e2878c91297395179cDan Gohman if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) 1844cf0dcfb44d9d308f2df48e2878c91297395179cDan Gohman continue; 1859e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands } 1869e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 1879e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands // Any remaining instructions need to be taken seriously! Check if they 1889e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands // read or write memory. 1899e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands if (I->mayWriteToMemory()) 1909e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands // Writes memory. Just give up. 1919e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands return false; 192cfd0ebea276521a48370c197e651064b032a381eDuncan Sands 1939e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands // If this instruction may read memory, remember that. 1949e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands ReadsMemory |= I->mayReadFromMemory(); 1959e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands } 1969e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands } 1979e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 1989e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands // Success! Functions in this SCC do not access memory, or only read memory. 1999e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands // Give them the appropriate attribute. 2009e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands bool MadeChange = false; 2012decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 2022decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner Function *F = (*I)->getFunction(); 2039e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 2049e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands if (F->doesNotAccessMemory()) 2059e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands // Already perfect! 2069e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands continue; 2079e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 2089e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands if (F->onlyReadsMemory() && ReadsMemory) 2099e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands // No change. 2109e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands continue; 2119e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 2129e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands MadeChange = true; 2139e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 2149e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands // Clear out any existing attributes. 215702cc91aa1bd41540e8674921ae7ac89a4ff061fBill Wendling AttrBuilder B; 216034b94b17006f51722886b0f2283fb6fb19aca1fBill Wendling B.addAttribute(Attribute::ReadOnly) 217034b94b17006f51722886b0f2283fb6fb19aca1fBill Wendling .addAttribute(Attribute::ReadNone); 2188246df61f6de716acf1f8c64fac3c19970a2c174Bill Wendling F->removeAttributes(AttributeSet::FunctionIndex, 2198246df61f6de716acf1f8c64fac3c19970a2c174Bill Wendling AttributeSet::get(F->getContext(), 2208246df61f6de716acf1f8c64fac3c19970a2c174Bill Wendling AttributeSet::FunctionIndex, B)); 2219e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 2229e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands // Add in the new attribute. 22399faa3b4ec6d03ac7808fe4ff3fbf3d04e375502Bill Wendling F->addAttribute(AttributeSet::FunctionIndex, 22470d2ca0725b05a2d372e4dc3336e8ea350093e98Bill Wendling ReadsMemory ? Attribute::ReadOnly : Attribute::ReadNone); 2259e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 2269e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands if (ReadsMemory) 227b2f2279056ab9e2e80f94c20d79affc007a4de62Duncan Sands ++NumReadOnly; 2289e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands else 229b2f2279056ab9e2e80f94c20d79affc007a4de62Duncan Sands ++NumReadNone; 2309e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands } 2319e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 2329e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands return MadeChange; 2339e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands} 2349e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 235b48a18903a5769f0ecb295db069252576b1388b0Nick Lewyckynamespace { 236b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // For a given pointer Argument, this retains a list of Arguments of functions 237b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // in the same SCC that the pointer data flows into. We use this to build an 238b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // SCC of the arguments. 239b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky struct ArgumentGraphNode { 240b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky Argument *Definition; 241b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky SmallVector<ArgumentGraphNode*, 4> Uses; 242b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky }; 243b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky 244b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky class ArgumentGraph { 245b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // We store pointers to ArgumentGraphNode objects, so it's important that 246b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // that they not move around upon insert. 247b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky typedef std::map<Argument*, ArgumentGraphNode> ArgumentMapTy; 248b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky 249b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky ArgumentMapTy ArgumentMap; 250b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky 251b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // There is no root node for the argument graph, in fact: 252b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // void f(int *x, int *y) { if (...) f(x, y); } 253b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // is an example where the graph is disconnected. The SCCIterator requires a 254b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // single entry point, so we maintain a fake ("synthetic") root node that 255b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // uses every node. Because the graph is directed and nothing points into 256b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // the root, it will not participate in any SCCs (except for its own). 257b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky ArgumentGraphNode SyntheticRoot; 258b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky 259b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky public: 260b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky ArgumentGraph() { SyntheticRoot.Definition = 0; } 261b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky 262b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky typedef SmallVectorImpl<ArgumentGraphNode*>::iterator iterator; 263b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky 264b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky iterator begin() { return SyntheticRoot.Uses.begin(); } 265b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky iterator end() { return SyntheticRoot.Uses.end(); } 266b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky ArgumentGraphNode *getEntryNode() { return &SyntheticRoot; } 267b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky 268b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky ArgumentGraphNode *operator[](Argument *A) { 269b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky ArgumentGraphNode &Node = ArgumentMap[A]; 270b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky Node.Definition = A; 271b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky SyntheticRoot.Uses.push_back(&Node); 272b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky return &Node; 273b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky } 274b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky }; 275b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky 276b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // This tracker checks whether callees are in the SCC, and if so it does not 277b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // consider that a capture, instead adding it to the "Uses" list and 278b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // continuing with the analysis. 279b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky struct ArgumentUsesTracker : public CaptureTracker { 280b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky ArgumentUsesTracker(const SmallPtrSet<Function*, 8> &SCCNodes) 281b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky : Captured(false), SCCNodes(SCCNodes) {} 282b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky 283b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky void tooManyUses() { Captured = true; } 284b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky 285b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky bool captured(Use *U) { 286b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky CallSite CS(U->getUser()); 287b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky if (!CS.getInstruction()) { Captured = true; return true; } 288b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky 289b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky Function *F = CS.getCalledFunction(); 290b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky if (!F || !SCCNodes.count(F)) { Captured = true; return true; } 291b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky 292b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end(); 293b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky for (CallSite::arg_iterator PI = CS.arg_begin(), PE = CS.arg_end(); 294b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky PI != PE; ++PI, ++AI) { 295b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky if (AI == AE) { 296b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky assert(F->isVarArg() && "More params than args in non-varargs call"); 297b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky Captured = true; 298b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky return true; 299b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky } 300b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky if (PI == U) { 301b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky Uses.push_back(AI); 302b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky break; 303b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky } 304b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky } 305b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky assert(!Uses.empty() && "Capturing call-site captured nothing?"); 306b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky return false; 307b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky } 308b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky 309b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky bool Captured; // True only if certainly captured (used outside our SCC). 310b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky SmallVector<Argument*, 4> Uses; // Uses within our SCC. 311b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky 312b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky const SmallPtrSet<Function*, 8> &SCCNodes; 313b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky }; 314b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky} 315b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky 316b48a18903a5769f0ecb295db069252576b1388b0Nick Lewyckynamespace llvm { 317b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky template<> struct GraphTraits<ArgumentGraphNode*> { 318b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky typedef ArgumentGraphNode NodeType; 319b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky typedef SmallVectorImpl<ArgumentGraphNode*>::iterator ChildIteratorType; 320b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky 321b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky static inline NodeType *getEntryNode(NodeType *A) { return A; } 322b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky static inline ChildIteratorType child_begin(NodeType *N) { 323b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky return N->Uses.begin(); 324b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky } 325b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky static inline ChildIteratorType child_end(NodeType *N) { 326b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky return N->Uses.end(); 327b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky } 328b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky }; 329b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky template<> struct GraphTraits<ArgumentGraph*> 330b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky : public GraphTraits<ArgumentGraphNode*> { 331b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky static NodeType *getEntryNode(ArgumentGraph *AG) { 332b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky return AG->getEntryNode(); 333b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky } 334b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky static ChildIteratorType nodes_begin(ArgumentGraph *AG) { 335b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky return AG->begin(); 336b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky } 337b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky static ChildIteratorType nodes_end(ArgumentGraph *AG) { 338b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky return AG->end(); 339b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky } 340b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky }; 341b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky} 342b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky 3439e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands/// AddNoCaptureAttrs - Deduce nocapture attributes for the SCC. 3442decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattnerbool FunctionAttrs::AddNoCaptureAttrs(const CallGraphSCC &SCC) { 3459e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands bool Changed = false; 3469e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 347b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky SmallPtrSet<Function*, 8> SCCNodes; 348b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky 349b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // Fill SCCNodes with the elements of the SCC. Used for quickly 350b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // looking up whether a given CallGraphNode is in this SCC. 351b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 352b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky Function *F = (*I)->getFunction(); 353b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky if (F && !F->isDeclaration() && !F->mayBeOverridden()) 354b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky SCCNodes.insert(F); 355b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky } 356b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky 357b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky ArgumentGraph AG; 358b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky 359702cc91aa1bd41540e8674921ae7ac89a4ff061fBill Wendling AttrBuilder B; 360034b94b17006f51722886b0f2283fb6fb19aca1fBill Wendling B.addAttribute(Attribute::NoCapture); 3617d2f2496c1d263eecdc104fd72e847a31d8695b9Bill Wendling 3629e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands // Check each function in turn, determining which pointer arguments are not 3639e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands // captured. 3642decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 3652decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner Function *F = (*I)->getFunction(); 3669e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 3679e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands if (F == 0) 368b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // External node - only a problem for arguments that we pass to it. 3699e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands continue; 3709e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 3719e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands // Definitions with weak linkage may be overridden at linktime with 372b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // something that captures pointers, so treat them like declarations. 3739e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands if (F->isDeclaration() || F->mayBeOverridden()) 3749e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands continue; 3759e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 376b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // Functions that are readonly (or readnone) and nounwind and don't return 377b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // a value can't capture arguments. Don't analyze them. 378b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky if (F->onlyReadsMemory() && F->doesNotThrow() && 379b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky F->getReturnType()->isVoidTy()) { 380b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); 381b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky A != E; ++A) { 382b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) { 38328d65722d6f283b327b5815914382077fe9c0ab4Bill Wendling A->addAttr(AttributeSet::get(F->getContext(), A->getArgNo() + 1, B)); 384b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky ++NumNoCapture; 385b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky Changed = true; 386b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky } 387b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky } 388b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky continue; 389b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky } 390b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky 3919e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A!=E; ++A) 392b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr()) { 393b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky ArgumentUsesTracker Tracker(SCCNodes); 394b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky PointerMayBeCaptured(A, &Tracker); 395b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky if (!Tracker.Captured) { 396b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky if (Tracker.Uses.empty()) { 397b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // If it's trivially not captured, mark it nocapture now. 39828d65722d6f283b327b5815914382077fe9c0ab4Bill Wendling A->addAttr(AttributeSet::get(F->getContext(), A->getArgNo()+1, B)); 399b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky ++NumNoCapture; 400b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky Changed = true; 401b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky } else { 402b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // If it's not trivially captured and not trivially not captured, 403b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // then it must be calling into another function in our SCC. Save 404b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // its particulars for Argument-SCC analysis later. 405b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky ArgumentGraphNode *Node = AG[A]; 406b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky for (SmallVectorImpl<Argument*>::iterator UI = Tracker.Uses.begin(), 407b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky UE = Tracker.Uses.end(); UI != UE; ++UI) 408b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky Node->Uses.push_back(AG[*UI]); 409b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky } 410b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky } 411b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // Otherwise, it's captured. Don't bother doing SCC analysis on it. 412b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky } 413b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky } 414b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky 415b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // The graph we've collected is partial because we stopped scanning for 416b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // argument uses once we solved the argument trivially. These partial nodes 417b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // show up as ArgumentGraphNode objects with an empty Uses list, and for 418b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // these nodes the final decision about whether they capture has already been 419b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // made. If the definition doesn't have a 'nocapture' attribute by now, it 420b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // captures. 421b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky 422b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky for (scc_iterator<ArgumentGraph*> I = scc_begin(&AG), E = scc_end(&AG); 423b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky I != E; ++I) { 424b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky std::vector<ArgumentGraphNode*> &ArgumentSCC = *I; 425b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky if (ArgumentSCC.size() == 1) { 426b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky if (!ArgumentSCC[0]->Definition) continue; // synthetic root node 427b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky 428b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // eg. "void f(int* x) { if (...) f(x); }" 429b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky if (ArgumentSCC[0]->Uses.size() == 1 && 430b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky ArgumentSCC[0]->Uses[0] == ArgumentSCC[0]) { 431cb3de0bc800d7920087b19bb12a545d4cc84114eBill Wendling ArgumentSCC[0]-> 432cb3de0bc800d7920087b19bb12a545d4cc84114eBill Wendling Definition-> 43328d65722d6f283b327b5815914382077fe9c0ab4Bill Wendling addAttr(AttributeSet::get(ArgumentSCC[0]->Definition->getContext(), 43428d65722d6f283b327b5815914382077fe9c0ab4Bill Wendling ArgumentSCC[0]->Definition->getArgNo() + 1, 43528d65722d6f283b327b5815914382077fe9c0ab4Bill Wendling B)); 4366b0568628319e08b36b8ec14793083e6bbf101a7Nick Lewycky ++NumNoCapture; 4379e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands Changed = true; 4389e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands } 439b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky continue; 440b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky } 441b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky 442b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky bool SCCCaptured = false; 443b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky for (std::vector<ArgumentGraphNode*>::iterator I = ArgumentSCC.begin(), 444b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky E = ArgumentSCC.end(); I != E && !SCCCaptured; ++I) { 445b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky ArgumentGraphNode *Node = *I; 446b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky if (Node->Uses.empty()) { 447b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky if (!Node->Definition->hasNoCaptureAttr()) 448b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky SCCCaptured = true; 449b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky } 450b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky } 451b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky if (SCCCaptured) continue; 452b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky 453b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky SmallPtrSet<Argument*, 8> ArgumentSCCNodes; 454b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // Fill ArgumentSCCNodes with the elements of the ArgumentSCC. Used for 455b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky // quickly looking up whether a given Argument is in this ArgumentSCC. 456b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky for (std::vector<ArgumentGraphNode*>::iterator I = ArgumentSCC.begin(), 457b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky E = ArgumentSCC.end(); I != E; ++I) { 458b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky ArgumentSCCNodes.insert((*I)->Definition); 459b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky } 460b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky 461b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky for (std::vector<ArgumentGraphNode*>::iterator I = ArgumentSCC.begin(), 462b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky E = ArgumentSCC.end(); I != E && !SCCCaptured; ++I) { 463b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky ArgumentGraphNode *N = *I; 464b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky for (SmallVectorImpl<ArgumentGraphNode*>::iterator UI = N->Uses.begin(), 465b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky UE = N->Uses.end(); UI != UE; ++UI) { 466b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky Argument *A = (*UI)->Definition; 467b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky if (A->hasNoCaptureAttr() || ArgumentSCCNodes.count(A)) 468b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky continue; 469b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky SCCCaptured = true; 470b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky break; 471b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky } 472b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky } 473b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky if (SCCCaptured) continue; 474b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky 475720ac9196997e856c5fed7a23fdfe144425222b1Nick Lewycky for (unsigned i = 0, e = ArgumentSCC.size(); i != e; ++i) { 476b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky Argument *A = ArgumentSCC[i]->Definition; 47728d65722d6f283b327b5815914382077fe9c0ab4Bill Wendling A->addAttr(AttributeSet::get(A->getContext(), A->getArgNo() + 1, B)); 478b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky ++NumNoCapture; 479b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky Changed = true; 480b48a18903a5769f0ecb295db069252576b1388b0Nick Lewycky } 4819e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands } 4829e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 4839e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands return Changed; 4849e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands} 4859e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands 486199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky/// IsFunctionMallocLike - A function is malloc-like if it returns either null 4874bfba9da0afb00ea1cc7df764da03ed9ebb7676bNick Lewycky/// or a pointer that doesn't alias any other pointer visible to the caller. 488199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewyckybool FunctionAttrs::IsFunctionMallocLike(Function *F, 48998a27ce03f092ab5464e65725f7d1fa0c03652f2Chris Lattner SmallPtrSet<Function*, 8> &SCCNodes) const { 490b4c9d9c51fcb8a4cad2336b1ad9d225f504bbc4cBenjamin Kramer SmallSetVector<Value *, 8> FlowsToReturn; 491199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) 492199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky if (ReturnInst *Ret = dyn_cast<ReturnInst>(I->getTerminator())) 493199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky FlowsToReturn.insert(Ret->getReturnValue()); 494199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky 495199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky for (unsigned i = 0; i != FlowsToReturn.size(); ++i) { 496b4c9d9c51fcb8a4cad2336b1ad9d225f504bbc4cBenjamin Kramer Value *RetVal = FlowsToReturn[i]; 497199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky 498199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky if (Constant *C = dyn_cast<Constant>(RetVal)) { 499199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky if (!C->isNullValue() && !isa<UndefValue>(C)) 500199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky return false; 501199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky 502199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky continue; 503199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky } 504199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky 505199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky if (isa<Argument>(RetVal)) 506199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky return false; 507199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky 508199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky if (Instruction *RVI = dyn_cast<Instruction>(RetVal)) 509199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky switch (RVI->getOpcode()) { 510199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky // Extend the analysis by looking upwards. 511199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky case Instruction::BitCast: 51283d63919bd990ce00f62e18114504b9e4a5cb35eVictor Hernandez case Instruction::GetElementPtr: 513199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky FlowsToReturn.insert(RVI->getOperand(0)); 514199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky continue; 515199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky case Instruction::Select: { 516199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky SelectInst *SI = cast<SelectInst>(RVI); 517199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky FlowsToReturn.insert(SI->getTrueValue()); 518199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky FlowsToReturn.insert(SI->getFalseValue()); 519439044f4f9594990fb9a8149ea67c119a2b05387Chris Lattner continue; 520439044f4f9594990fb9a8149ea67c119a2b05387Chris Lattner } 521199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky case Instruction::PHI: { 522199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky PHINode *PN = cast<PHINode>(RVI); 523199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 524199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky FlowsToReturn.insert(PN->getIncomingValue(i)); 525439044f4f9594990fb9a8149ea67c119a2b05387Chris Lattner continue; 526439044f4f9594990fb9a8149ea67c119a2b05387Chris Lattner } 527199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky 528199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky // Check whether the pointer came from an allocation. 529199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky case Instruction::Alloca: 530199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky break; 531199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky case Instruction::Call: 532199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky case Instruction::Invoke: { 533199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky CallSite CS(RVI); 534034b94b17006f51722886b0f2283fb6fb19aca1fBill Wendling if (CS.paramHasAttr(0, Attribute::NoAlias)) 535199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky break; 536199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky if (CS.getCalledFunction() && 53798a27ce03f092ab5464e65725f7d1fa0c03652f2Chris Lattner SCCNodes.count(CS.getCalledFunction())) 538199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky break; 539199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky } // fall-through 540199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky default: 541199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky return false; // Did not come from an allocation. 542199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky } 543199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky 544f94b5edc452c32d9ae258e7de30c33391fda6cc9Dan Gohman if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false)) 545199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky return false; 546199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky } 547199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky 548199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky return true; 549199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky} 550199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky 551199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky/// AddNoAliasAttrs - Deduce noalias attributes for the SCC. 5522decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattnerbool FunctionAttrs::AddNoAliasAttrs(const CallGraphSCC &SCC) { 55398a27ce03f092ab5464e65725f7d1fa0c03652f2Chris Lattner SmallPtrSet<Function*, 8> SCCNodes; 554199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky 555199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky // Fill SCCNodes with the elements of the SCC. Used for quickly 556199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky // looking up whether a given CallGraphNode is in this SCC. 5572decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) 5582decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner SCCNodes.insert((*I)->getFunction()); 559199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky 5604bfba9da0afb00ea1cc7df764da03ed9ebb7676bNick Lewycky // Check each function in turn, determining which functions return noalias 5614bfba9da0afb00ea1cc7df764da03ed9ebb7676bNick Lewycky // pointers. 5622decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 5632decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner Function *F = (*I)->getFunction(); 564199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky 565199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky if (F == 0) 566199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky // External node - skip it; 567199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky return false; 568199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky 569199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky // Already noalias. 570199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky if (F->doesNotAlias(0)) 571199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky continue; 572199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky 573199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky // Definitions with weak linkage may be overridden at linktime, so 574199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky // treat them like declarations. 575199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky if (F->isDeclaration() || F->mayBeOverridden()) 576199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky return false; 577199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky 578199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky // We annotate noalias return values, which are only applicable to 579199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky // pointer types. 5801df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if (!F->getReturnType()->isPointerTy()) 581199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky continue; 582199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky 583199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky if (!IsFunctionMallocLike(F, SCCNodes)) 584199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky return false; 585199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky } 586199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky 587199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky bool MadeChange = false; 5882decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 5892decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattner Function *F = (*I)->getFunction(); 5901df9859c40492511b8aa4321eb76496005d3b75bDuncan Sands if (F->doesNotAlias(0) || !F->getReturnType()->isPointerTy()) 591199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky continue; 592199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky 593199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky F->setDoesNotAlias(0); 594199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky ++NumNoAlias; 595199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky MadeChange = true; 596199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky } 597199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky 598199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky return MadeChange; 599199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky} 600199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky 6012decb22222cac46bb1d9163e7b89d7e5be8ef65fChris Lattnerbool FunctionAttrs::runOnSCC(CallGraphSCC &SCC) { 6023c97f7af9e75507f12a3977bced6b91c7e2ffb2aDan Gohman AA = &getAnalysis<AliasAnalysis>(); 6033c97f7af9e75507f12a3977bced6b91c7e2ffb2aDan Gohman 6049e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands bool Changed = AddReadAttrs(SCC); 6059e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands Changed |= AddNoCaptureAttrs(SCC); 606199aa3c09c6ec42da6165c5ba1415aaeeaf7c11fNick Lewycky Changed |= AddNoAliasAttrs(SCC); 6079e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands return Changed; 6089e89ba31f16a960239a750a26a982b4c9dfe8949Duncan Sands} 609