LLVM API Documentation
00001 //===- FunctionAttrs.cpp - Pass which marks functions readnone or readonly ===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements a simple interprocedural pass which walks the 00011 // call-graph, looking for functions which do not access or only read 00012 // non-local memory, and marking them readnone/readonly. In addition, 00013 // it marks function arguments (of pointer type) 'nocapture' if a call 00014 // to the function does not create any copies of the pointer value that 00015 // outlive the call. This more or less means that the pointer is only 00016 // dereferenced, and not returned from the function or stored in a global. 00017 // This pass is implemented as a bottom-up traversal of the call-graph. 00018 // 00019 //===----------------------------------------------------------------------===// 00020 00021 #define DEBUG_TYPE "functionattrs" 00022 #include "llvm/Transforms/IPO.h" 00023 #include "llvm/CallGraphSCCPass.h" 00024 #include "llvm/GlobalVariable.h" 00025 #include "llvm/IntrinsicInst.h" 00026 #include "llvm/Analysis/AliasAnalysis.h" 00027 #include "llvm/Analysis/CallGraph.h" 00028 #include "llvm/Analysis/CaptureTracking.h" 00029 #include "llvm/ADT/SmallSet.h" 00030 #include "llvm/ADT/Statistic.h" 00031 #include "llvm/ADT/UniqueVector.h" 00032 #include "llvm/Support/Compiler.h" 00033 #include "llvm/Support/InstIterator.h" 00034 using namespace llvm; 00035 00036 STATISTIC(NumReadNone, "Number of functions marked readnone"); 00037 STATISTIC(NumReadOnly, "Number of functions marked readonly"); 00038 STATISTIC(NumNoCapture, "Number of arguments marked nocapture"); 00039 STATISTIC(NumNoAlias, "Number of function returns marked noalias"); 00040 00041 namespace { 00042 struct VISIBILITY_HIDDEN FunctionAttrs : public CallGraphSCCPass { 00043 static char ID; // Pass identification, replacement for typeid 00044 FunctionAttrs() : CallGraphSCCPass(&ID) {} 00045 00046 // runOnSCC - Analyze the SCC, performing the transformation if possible. 00047 bool runOnSCC(const std::vector<CallGraphNode *> &SCC); 00048 00049 // AddReadAttrs - Deduce readonly/readnone attributes for the SCC. 00050 bool AddReadAttrs(const std::vector<CallGraphNode *> &SCC); 00051 00052 // AddNoCaptureAttrs - Deduce nocapture attributes for the SCC. 00053 bool AddNoCaptureAttrs(const std::vector<CallGraphNode *> &SCC); 00054 00055 // IsFunctionMallocLike - Does this function allocate new memory? 00056 bool IsFunctionMallocLike(Function *F, 00057 SmallPtrSet<CallGraphNode*, 8> &) const; 00058 00059 // AddNoAliasAttrs - Deduce noalias attributes for the SCC. 00060 bool AddNoAliasAttrs(const std::vector<CallGraphNode *> &SCC); 00061 00062 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00063 AU.setPreservesCFG(); 00064 CallGraphSCCPass::getAnalysisUsage(AU); 00065 } 00066 00067 bool PointsToLocalMemory(Value *V); 00068 }; 00069 } 00070 00071 char FunctionAttrs::ID = 0; 00072 static RegisterPass<FunctionAttrs> 00073 X("functionattrs", "Deduce function attributes"); 00074 00075 Pass *llvm::createFunctionAttrsPass() { return new FunctionAttrs(); } 00076 00077 00078 /// PointsToLocalMemory - Returns whether the given pointer value points to 00079 /// memory that is local to the function. Global constants are considered 00080 /// local to all functions. 00081 bool FunctionAttrs::PointsToLocalMemory(Value *V) { 00082 V = V->getUnderlyingObject(); 00083 // An alloca instruction defines local memory. 00084 if (isa<AllocaInst>(V)) 00085 return true; 00086 // A global constant counts as local memory for our purposes. 00087 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) 00088 return GV->isConstant(); 00089 // Could look through phi nodes and selects here, but it doesn't seem 00090 // to be useful in practice. 00091 return false; 00092 } 00093 00094 /// AddReadAttrs - Deduce readonly/readnone attributes for the SCC. 00095 bool FunctionAttrs::AddReadAttrs(const std::vector<CallGraphNode *> &SCC) { 00096 SmallPtrSet<CallGraphNode*, 8> SCCNodes; 00097 CallGraph &CG = getAnalysis<CallGraph>(); 00098 00099 // Fill SCCNodes with the elements of the SCC. Used for quickly 00100 // looking up whether a given CallGraphNode is in this SCC. 00101 for (unsigned i = 0, e = SCC.size(); i != e; ++i) 00102 SCCNodes.insert(SCC[i]); 00103 00104 // Check if any of the functions in the SCC read or write memory. If they 00105 // write memory then they can't be marked readnone or readonly. 00106 bool ReadsMemory = false; 00107 for (unsigned i = 0, e = SCC.size(); i != e; ++i) { 00108 Function *F = SCC[i]->getFunction(); 00109 00110 if (F == 0) 00111 // External node - may write memory. Just give up. 00112 return false; 00113 00114 if (F->doesNotAccessMemory()) 00115 // Already perfect! 00116 continue; 00117 00118 // Definitions with weak linkage may be overridden at linktime with 00119 // something that writes memory, so treat them like declarations. 00120 if (F->isDeclaration() || F->mayBeOverridden()) { 00121 if (!F->onlyReadsMemory()) 00122 // May write memory. Just give up. 00123 return false; 00124 00125 ReadsMemory = true; 00126 continue; 00127 } 00128 00129 // Scan the function body for instructions that may read or write memory. 00130 for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) { 00131 Instruction *I = &*II; 00132 00133 // Some instructions can be ignored even if they read or write memory. 00134 // Detect these now, skipping to the next instruction if one is found. 00135 CallSite CS = CallSite::get(I); 00136 if (CS.getInstruction()) { 00137 // Ignore calls to functions in the same SCC. 00138 if (SCCNodes.count(CG[CS.getCalledFunction()])) 00139 continue; 00140 } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 00141 // Ignore loads from local memory. 00142 if (PointsToLocalMemory(LI->getPointerOperand())) 00143 continue; 00144 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 00145 // Ignore stores to local memory. 00146 if (PointsToLocalMemory(SI->getPointerOperand())) 00147 continue; 00148 } 00149 00150 // Any remaining instructions need to be taken seriously! Check if they 00151 // read or write memory. 00152 if (I->mayWriteToMemory()) 00153 // Writes memory. Just give up. 00154 return false; 00155 00156 if (isa<MallocInst>(I)) 00157 // MallocInst claims not to write memory! PR3754. 00158 return false; 00159 00160 // If this instruction may read memory, remember that. 00161 ReadsMemory |= I->mayReadFromMemory(); 00162 } 00163 } 00164 00165 // Success! Functions in this SCC do not access memory, or only read memory. 00166 // Give them the appropriate attribute. 00167 bool MadeChange = false; 00168 for (unsigned i = 0, e = SCC.size(); i != e; ++i) { 00169 Function *F = SCC[i]->getFunction(); 00170 00171 if (F->doesNotAccessMemory()) 00172 // Already perfect! 00173 continue; 00174 00175 if (F->onlyReadsMemory() && ReadsMemory) 00176 // No change. 00177 continue; 00178 00179 MadeChange = true; 00180 00181 // Clear out any existing attributes. 00182 F->removeAttribute(~0, Attribute::ReadOnly | Attribute::ReadNone); 00183 00184 // Add in the new attribute. 00185 F->addAttribute(~0, ReadsMemory? Attribute::ReadOnly : Attribute::ReadNone); 00186 00187 if (ReadsMemory) 00188 ++NumReadOnly; 00189 else 00190 ++NumReadNone; 00191 } 00192 00193 return MadeChange; 00194 } 00195 00196 /// AddNoCaptureAttrs - Deduce nocapture attributes for the SCC. 00197 bool FunctionAttrs::AddNoCaptureAttrs(const std::vector<CallGraphNode *> &SCC) { 00198 bool Changed = false; 00199 00200 // Check each function in turn, determining which pointer arguments are not 00201 // captured. 00202 for (unsigned i = 0, e = SCC.size(); i != e; ++i) { 00203 Function *F = SCC[i]->getFunction(); 00204 00205 if (F == 0) 00206 // External node - skip it; 00207 continue; 00208 00209 // Definitions with weak linkage may be overridden at linktime with 00210 // something that writes memory, so treat them like declarations. 00211 if (F->isDeclaration() || F->mayBeOverridden()) 00212 continue; 00213 00214 for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A!=E; ++A) 00215 if (isa<PointerType>(A->getType()) && !A->hasNoCaptureAttr() && 00216 !PointerMayBeCaptured(A, true)) { 00217 A->addAttr(Attribute::NoCapture); 00218 ++NumNoCapture; 00219 Changed = true; 00220 } 00221 } 00222 00223 return Changed; 00224 } 00225 00226 /// IsFunctionMallocLike - A function is malloc-like if it returns either null 00227 /// or a pointer that doesn't alias any other pointer visible to the caller. 00228 bool FunctionAttrs::IsFunctionMallocLike(Function *F, 00229 SmallPtrSet<CallGraphNode*, 8> &SCCNodes) const { 00230 CallGraph &CG = getAnalysis<CallGraph>(); 00231 00232 UniqueVector<Value *> FlowsToReturn; 00233 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) 00234 if (ReturnInst *Ret = dyn_cast<ReturnInst>(I->getTerminator())) 00235 FlowsToReturn.insert(Ret->getReturnValue()); 00236 00237 for (unsigned i = 0; i != FlowsToReturn.size(); ++i) { 00238 Value *RetVal = FlowsToReturn[i+1]; // UniqueVector[0] is reserved. 00239 00240 if (Constant *C = dyn_cast<Constant>(RetVal)) { 00241 if (!C->isNullValue() && !isa<UndefValue>(C)) 00242 return false; 00243 00244 continue; 00245 } 00246 00247 if (isa<Argument>(RetVal)) 00248 return false; 00249 00250 if (Instruction *RVI = dyn_cast<Instruction>(RetVal)) 00251 switch (RVI->getOpcode()) { 00252 // Extend the analysis by looking upwards. 00253 case Instruction::GetElementPtr: 00254 case Instruction::BitCast: 00255 FlowsToReturn.insert(RVI->getOperand(0)); 00256 continue; 00257 case Instruction::Select: { 00258 SelectInst *SI = cast<SelectInst>(RVI); 00259 FlowsToReturn.insert(SI->getTrueValue()); 00260 FlowsToReturn.insert(SI->getFalseValue()); 00261 } continue; 00262 case Instruction::PHI: { 00263 PHINode *PN = cast<PHINode>(RVI); 00264 for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 00265 FlowsToReturn.insert(PN->getIncomingValue(i)); 00266 } continue; 00267 00268 // Check whether the pointer came from an allocation. 00269 case Instruction::Alloca: 00270 case Instruction::Malloc: 00271 break; 00272 case Instruction::Call: 00273 case Instruction::Invoke: { 00274 CallSite CS(RVI); 00275 if (CS.paramHasAttr(0, Attribute::NoAlias)) 00276 break; 00277 if (CS.getCalledFunction() && 00278 SCCNodes.count(CG[CS.getCalledFunction()])) 00279 break; 00280 } // fall-through 00281 default: 00282 return false; // Did not come from an allocation. 00283 } 00284 00285 if (PointerMayBeCaptured(RetVal, false)) 00286 return false; 00287 } 00288 00289 return true; 00290 } 00291 00292 /// AddNoAliasAttrs - Deduce noalias attributes for the SCC. 00293 bool FunctionAttrs::AddNoAliasAttrs(const std::vector<CallGraphNode *> &SCC) { 00294 SmallPtrSet<CallGraphNode*, 8> SCCNodes; 00295 00296 // Fill SCCNodes with the elements of the SCC. Used for quickly 00297 // looking up whether a given CallGraphNode is in this SCC. 00298 for (unsigned i = 0, e = SCC.size(); i != e; ++i) 00299 SCCNodes.insert(SCC[i]); 00300 00301 // Check each function in turn, determining which functions return noalias 00302 // pointers. 00303 for (unsigned i = 0, e = SCC.size(); i != e; ++i) { 00304 Function *F = SCC[i]->getFunction(); 00305 00306 if (F == 0) 00307 // External node - skip it; 00308 return false; 00309 00310 // Already noalias. 00311 if (F->doesNotAlias(0)) 00312 continue; 00313 00314 // Definitions with weak linkage may be overridden at linktime, so 00315 // treat them like declarations. 00316 if (F->isDeclaration() || F->mayBeOverridden()) 00317 return false; 00318 00319 // We annotate noalias return values, which are only applicable to 00320 // pointer types. 00321 if (!isa<PointerType>(F->getReturnType())) 00322 continue; 00323 00324 if (!IsFunctionMallocLike(F, SCCNodes)) 00325 return false; 00326 } 00327 00328 bool MadeChange = false; 00329 for (unsigned i = 0, e = SCC.size(); i != e; ++i) { 00330 Function *F = SCC[i]->getFunction(); 00331 if (F->doesNotAlias(0) || !isa<PointerType>(F->getReturnType())) 00332 continue; 00333 00334 F->setDoesNotAlias(0); 00335 ++NumNoAlias; 00336 MadeChange = true; 00337 } 00338 00339 return MadeChange; 00340 } 00341 00342 bool FunctionAttrs::runOnSCC(const std::vector<CallGraphNode *> &SCC) { 00343 bool Changed = AddReadAttrs(SCC); 00344 Changed |= AddNoCaptureAttrs(SCC); 00345 Changed |= AddNoAliasAttrs(SCC); 00346 return Changed; 00347 }