FunctionAttrs.cpp revision ae0a7bc68303ce0c8721f0e981ae602601390e68
1//===- FunctionAttrs.cpp - Pass which marks functions readnone or readonly ===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements a simple interprocedural pass which walks the 11// call-graph, looking for functions which do not access or only read 12// non-local memory, and marking them readnone/readonly. In addition, 13// it marks function arguments (of pointer type) 'nocapture' if a call 14// to the function does not create any copies of the pointer value that 15// outlive the call. This more or less means that the pointer is only 16// dereferenced, and not returned from the function or stored in a global. 17// This pass is implemented as a bottom-up traversal of the call-graph. 18// 19//===----------------------------------------------------------------------===// 20 21#define DEBUG_TYPE "functionattrs" 22#include "llvm/Transforms/IPO.h" 23#include "llvm/CallGraphSCCPass.h" 24#include "llvm/GlobalVariable.h" 25#include "llvm/IntrinsicInst.h" 26#include "llvm/Analysis/AliasAnalysis.h" 27#include "llvm/Analysis/CallGraph.h" 28#include "llvm/Analysis/CaptureTracking.h" 29#include "llvm/Analysis/MemoryBuiltins.h" 30#include "llvm/ADT/SmallSet.h" 31#include "llvm/ADT/Statistic.h" 32#include "llvm/ADT/UniqueVector.h" 33#include "llvm/Support/InstIterator.h" 34using namespace llvm; 35 36STATISTIC(NumReadNone, "Number of functions marked readnone"); 37STATISTIC(NumReadOnly, "Number of functions marked readonly"); 38STATISTIC(NumNoCapture, "Number of arguments marked nocapture"); 39STATISTIC(NumNoAlias, "Number of function returns marked noalias"); 40 41namespace { 42 struct FunctionAttrs : public CallGraphSCCPass { 43 static char ID; // Pass identification, replacement for typeid 44 FunctionAttrs() : CallGraphSCCPass(ID) {} 45 46 // runOnSCC - Analyze the SCC, performing the transformation if possible. 47 bool runOnSCC(CallGraphSCC &SCC); 48 49 // AddReadAttrs - Deduce readonly/readnone attributes for the SCC. 50 bool AddReadAttrs(const CallGraphSCC &SCC); 51 52 // AddNoCaptureAttrs - Deduce nocapture attributes for the SCC. 53 bool AddNoCaptureAttrs(const CallGraphSCC &SCC); 54 55 // IsFunctionMallocLike - Does this function allocate new memory? 56 bool IsFunctionMallocLike(Function *F, 57 SmallPtrSet<Function*, 8> &) const; 58 59 // AddNoAliasAttrs - Deduce noalias attributes for the SCC. 60 bool AddNoAliasAttrs(const CallGraphSCC &SCC); 61 62 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 63 AU.setPreservesCFG(); 64 CallGraphSCCPass::getAnalysisUsage(AU); 65 } 66 67 bool PointsToLocalMemory(Value *V); 68 }; 69} 70 71char FunctionAttrs::ID = 0; 72INITIALIZE_PASS_BEGIN(FunctionAttrs, "functionattrs", 73 "Deduce function attributes", false, false) 74INITIALIZE_AG_DEPENDENCY(CallGraph) 75INITIALIZE_PASS_END(FunctionAttrs, "functionattrs", 76 "Deduce function attributes", false, false) 77 78Pass *llvm::createFunctionAttrsPass() { return new FunctionAttrs(); } 79 80 81/// PointsToLocalMemory - Returns whether the given pointer value points to 82/// memory that is local to the function. Global constants are considered 83/// local to all functions. 84bool FunctionAttrs::PointsToLocalMemory(Value *V) { 85 SmallVector<Value*, 16> Worklist; 86 unsigned MaxLookup = 8; 87 88 Worklist.push_back(V); 89 90 do { 91 V = Worklist.pop_back_val()->getUnderlyingObject(); 92 93 // An alloca instruction defines local memory. 94 if (isa<AllocaInst>(V)) 95 continue; 96 97 // A global constant counts as local memory for our purposes. 98 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) { 99 if (!GV->isConstant()) 100 return false; 101 continue; 102 } 103 104 // If both select values point to local memory, then so does the select. 105 if (SelectInst *SI = dyn_cast<SelectInst>(V)) { 106 Worklist.push_back(SI->getTrueValue()); 107 Worklist.push_back(SI->getFalseValue()); 108 continue; 109 } 110 111 // If all values incoming to a phi node point to local memory, then so does 112 // the phi. 113 if (PHINode *PN = dyn_cast<PHINode>(V)) { 114 // Don't bother inspecting phi nodes with many operands. 115 if (PN->getNumIncomingValues() > MaxLookup) 116 return false; 117 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 118 Worklist.push_back(PN->getIncomingValue(i)); 119 continue; 120 } 121 122 return false; 123 } while (!Worklist.empty() && --MaxLookup); 124 125 return Worklist.empty(); 126} 127 128/// AddReadAttrs - Deduce readonly/readnone attributes for the SCC. 129bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) { 130 SmallPtrSet<Function*, 8> SCCNodes; 131 132 // Fill SCCNodes with the elements of the SCC. Used for quickly 133 // looking up whether a given CallGraphNode is in this SCC. 134 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) 135 SCCNodes.insert((*I)->getFunction()); 136 137 // Check if any of the functions in the SCC read or write memory. If they 138 // write memory then they can't be marked readnone or readonly. 139 bool ReadsMemory = false; 140 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 141 Function *F = (*I)->getFunction(); 142 143 if (F == 0) 144 // External node - may write memory. Just give up. 145 return false; 146 147 if (F->doesNotAccessMemory()) 148 // Already perfect! 149 continue; 150 151 // Definitions with weak linkage may be overridden at linktime with 152 // something that writes memory, so treat them like declarations. 153 if (F->isDeclaration() || F->mayBeOverridden()) { 154 if (!F->onlyReadsMemory()) 155 // May write memory. Just give up. 156 return false; 157 158 ReadsMemory = true; 159 continue; 160 } 161 162 // Scan the function body for instructions that may read or write memory. 163 for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) { 164 Instruction *I = &*II; 165 166 // Some instructions can be ignored even if they read or write memory. 167 // Detect these now, skipping to the next instruction if one is found. 168 CallSite CS(cast<Value>(I)); 169 if (CS && CS.getCalledFunction()) { 170 // Ignore calls to functions in the same SCC. 171 if (SCCNodes.count(CS.getCalledFunction())) 172 continue; 173 // Ignore intrinsics that only access local memory. 174 if (unsigned id = CS.getCalledFunction()->getIntrinsicID()) 175 if (AliasAnalysis::getIntrinsicModRefBehavior(id) == 176 AliasAnalysis::AccessesArguments) { 177 // Check that all pointer arguments point to local memory. 178 for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 179 CI != CE; ++CI) { 180 Value *Arg = *CI; 181 if (Arg->getType()->isPointerTy() && !PointsToLocalMemory(Arg)) 182 // Writes memory. Just give up. 183 return false; 184 } 185 // Only reads and writes local memory. 186 continue; 187 } 188 } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 189 // Ignore loads from local memory. 190 if (PointsToLocalMemory(LI->getPointerOperand())) 191 continue; 192 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 193 // Ignore stores to local memory. 194 if (PointsToLocalMemory(SI->getPointerOperand())) 195 continue; 196 } 197 198 // Any remaining instructions need to be taken seriously! Check if they 199 // read or write memory. 200 if (I->mayWriteToMemory()) 201 // Writes memory. Just give up. 202 return false; 203 204 if (isMalloc(I)) 205 // malloc claims not to write memory! PR3754. 206 return false; 207 208 // If this instruction may read memory, remember that. 209 ReadsMemory |= I->mayReadFromMemory(); 210 } 211 } 212 213 // Success! Functions in this SCC do not access memory, or only read memory. 214 // Give them the appropriate attribute. 215 bool MadeChange = false; 216 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 217 Function *F = (*I)->getFunction(); 218 219 if (F->doesNotAccessMemory()) 220 // Already perfect! 221 continue; 222 223 if (F->onlyReadsMemory() && ReadsMemory) 224 // No change. 225 continue; 226 227 MadeChange = true; 228 229 // Clear out any existing attributes. 230 F->removeAttribute(~0, Attribute::ReadOnly | Attribute::ReadNone); 231 232 // Add in the new attribute. 233 F->addAttribute(~0, ReadsMemory? Attribute::ReadOnly : Attribute::ReadNone); 234 235 if (ReadsMemory) 236 ++NumReadOnly; 237 else 238 ++NumReadNone; 239 } 240 241 return MadeChange; 242} 243 244/// AddNoCaptureAttrs - Deduce nocapture attributes for the SCC. 245bool FunctionAttrs::AddNoCaptureAttrs(const CallGraphSCC &SCC) { 246 bool Changed = false; 247 248 // Check each function in turn, determining which pointer arguments are not 249 // captured. 250 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 251 Function *F = (*I)->getFunction(); 252 253 if (F == 0) 254 // External node - skip it; 255 continue; 256 257 // Definitions with weak linkage may be overridden at linktime with 258 // something that writes memory, so treat them like declarations. 259 if (F->isDeclaration() || F->mayBeOverridden()) 260 continue; 261 262 for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A!=E; ++A) 263 if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr() && 264 !PointerMayBeCaptured(A, true, /*StoreCaptures=*/false)) { 265 A->addAttr(Attribute::NoCapture); 266 ++NumNoCapture; 267 Changed = true; 268 } 269 } 270 271 return Changed; 272} 273 274/// IsFunctionMallocLike - A function is malloc-like if it returns either null 275/// or a pointer that doesn't alias any other pointer visible to the caller. 276bool FunctionAttrs::IsFunctionMallocLike(Function *F, 277 SmallPtrSet<Function*, 8> &SCCNodes) const { 278 UniqueVector<Value *> FlowsToReturn; 279 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) 280 if (ReturnInst *Ret = dyn_cast<ReturnInst>(I->getTerminator())) 281 FlowsToReturn.insert(Ret->getReturnValue()); 282 283 for (unsigned i = 0; i != FlowsToReturn.size(); ++i) { 284 Value *RetVal = FlowsToReturn[i+1]; // UniqueVector[0] is reserved. 285 286 if (Constant *C = dyn_cast<Constant>(RetVal)) { 287 if (!C->isNullValue() && !isa<UndefValue>(C)) 288 return false; 289 290 continue; 291 } 292 293 if (isa<Argument>(RetVal)) 294 return false; 295 296 if (Instruction *RVI = dyn_cast<Instruction>(RetVal)) 297 switch (RVI->getOpcode()) { 298 // Extend the analysis by looking upwards. 299 case Instruction::BitCast: 300 case Instruction::GetElementPtr: 301 FlowsToReturn.insert(RVI->getOperand(0)); 302 continue; 303 case Instruction::Select: { 304 SelectInst *SI = cast<SelectInst>(RVI); 305 FlowsToReturn.insert(SI->getTrueValue()); 306 FlowsToReturn.insert(SI->getFalseValue()); 307 continue; 308 } 309 case Instruction::PHI: { 310 PHINode *PN = cast<PHINode>(RVI); 311 for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 312 FlowsToReturn.insert(PN->getIncomingValue(i)); 313 continue; 314 } 315 316 // Check whether the pointer came from an allocation. 317 case Instruction::Alloca: 318 break; 319 case Instruction::Call: 320 case Instruction::Invoke: { 321 CallSite CS(RVI); 322 if (CS.paramHasAttr(0, Attribute::NoAlias)) 323 break; 324 if (CS.getCalledFunction() && 325 SCCNodes.count(CS.getCalledFunction())) 326 break; 327 } // fall-through 328 default: 329 return false; // Did not come from an allocation. 330 } 331 332 if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false)) 333 return false; 334 } 335 336 return true; 337} 338 339/// AddNoAliasAttrs - Deduce noalias attributes for the SCC. 340bool FunctionAttrs::AddNoAliasAttrs(const CallGraphSCC &SCC) { 341 SmallPtrSet<Function*, 8> SCCNodes; 342 343 // Fill SCCNodes with the elements of the SCC. Used for quickly 344 // looking up whether a given CallGraphNode is in this SCC. 345 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) 346 SCCNodes.insert((*I)->getFunction()); 347 348 // Check each function in turn, determining which functions return noalias 349 // pointers. 350 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 351 Function *F = (*I)->getFunction(); 352 353 if (F == 0) 354 // External node - skip it; 355 return false; 356 357 // Already noalias. 358 if (F->doesNotAlias(0)) 359 continue; 360 361 // Definitions with weak linkage may be overridden at linktime, so 362 // treat them like declarations. 363 if (F->isDeclaration() || F->mayBeOverridden()) 364 return false; 365 366 // We annotate noalias return values, which are only applicable to 367 // pointer types. 368 if (!F->getReturnType()->isPointerTy()) 369 continue; 370 371 if (!IsFunctionMallocLike(F, SCCNodes)) 372 return false; 373 } 374 375 bool MadeChange = false; 376 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 377 Function *F = (*I)->getFunction(); 378 if (F->doesNotAlias(0) || !F->getReturnType()->isPointerTy()) 379 continue; 380 381 F->setDoesNotAlias(0); 382 ++NumNoAlias; 383 MadeChange = true; 384 } 385 386 return MadeChange; 387} 388 389bool FunctionAttrs::runOnSCC(CallGraphSCC &SCC) { 390 bool Changed = AddReadAttrs(SCC); 391 Changed |= AddNoCaptureAttrs(SCC); 392 Changed |= AddNoAliasAttrs(SCC); 393 return Changed; 394} 395