FunctionAttrs.cpp revision 860847553460378e38db1bf8dac7ef4ad4daafc7
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/ADT/SmallSet.h" 30#include "llvm/ADT/Statistic.h" 31#include "llvm/ADT/UniqueVector.h" 32#include "llvm/Support/InstIterator.h" 33using namespace llvm; 34 35STATISTIC(NumReadNone, "Number of functions marked readnone"); 36STATISTIC(NumReadOnly, "Number of functions marked readonly"); 37STATISTIC(NumNoCapture, "Number of arguments marked nocapture"); 38STATISTIC(NumNoAlias, "Number of function returns marked noalias"); 39 40namespace { 41 struct FunctionAttrs : public CallGraphSCCPass { 42 static char ID; // Pass identification, replacement for typeid 43 FunctionAttrs() : CallGraphSCCPass(ID) { 44 initializeFunctionAttrsPass(*PassRegistry::getPassRegistry()); 45 } 46 47 // runOnSCC - Analyze the SCC, performing the transformation if possible. 48 bool runOnSCC(CallGraphSCC &SCC); 49 50 // AddReadAttrs - Deduce readonly/readnone attributes for the SCC. 51 bool AddReadAttrs(const CallGraphSCC &SCC); 52 53 // AddNoCaptureAttrs - Deduce nocapture attributes for the SCC. 54 bool AddNoCaptureAttrs(const CallGraphSCC &SCC); 55 56 // IsFunctionMallocLike - Does this function allocate new memory? 57 bool IsFunctionMallocLike(Function *F, 58 SmallPtrSet<Function*, 8> &) const; 59 60 // AddNoAliasAttrs - Deduce noalias attributes for the SCC. 61 bool AddNoAliasAttrs(const CallGraphSCC &SCC); 62 63 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 64 AU.setPreservesCFG(); 65 CallGraphSCCPass::getAnalysisUsage(AU); 66 } 67 68 bool PointsToLocalOrConstantMemory(Value *V); 69 }; 70} 71 72char FunctionAttrs::ID = 0; 73INITIALIZE_PASS_BEGIN(FunctionAttrs, "functionattrs", 74 "Deduce function attributes", false, false) 75INITIALIZE_AG_DEPENDENCY(CallGraph) 76INITIALIZE_PASS_END(FunctionAttrs, "functionattrs", 77 "Deduce function attributes", false, false) 78 79Pass *llvm::createFunctionAttrsPass() { return new FunctionAttrs(); } 80 81 82/// PointsToLocalOrConstantMemory - Returns whether the given pointer value 83/// points to memory that is local to the function, with global constants being 84/// considered local to all functions. 85bool FunctionAttrs::PointsToLocalOrConstantMemory(Value *V) { 86 SmallVector<Value*, 16> Worklist; 87 unsigned MaxLookup = 8; 88 89 Worklist.push_back(V); 90 91 do { 92 V = Worklist.pop_back_val()->getUnderlyingObject(); 93 94 // An alloca instruction defines local memory. 95 if (isa<AllocaInst>(V)) 96 continue; 97 98 // A global constant counts as local memory for our purposes. 99 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) { 100 if (!GV->isConstant()) 101 return false; 102 continue; 103 } 104 105 // If both select values point to local memory, then so does the select. 106 if (SelectInst *SI = dyn_cast<SelectInst>(V)) { 107 Worklist.push_back(SI->getTrueValue()); 108 Worklist.push_back(SI->getFalseValue()); 109 continue; 110 } 111 112 // If all values incoming to a phi node point to local memory, then so does 113 // the phi. 114 if (PHINode *PN = dyn_cast<PHINode>(V)) { 115 // Don't bother inspecting phi nodes with many operands. 116 if (PN->getNumIncomingValues() > MaxLookup) 117 return false; 118 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 119 Worklist.push_back(PN->getIncomingValue(i)); 120 continue; 121 } 122 123 return false; 124 } while (!Worklist.empty() && --MaxLookup); 125 126 return Worklist.empty(); 127} 128 129/// AddReadAttrs - Deduce readonly/readnone attributes for the SCC. 130bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) { 131 SmallPtrSet<Function*, 8> SCCNodes; 132 133 // Fill SCCNodes with the elements of the SCC. Used for quickly 134 // looking up whether a given CallGraphNode is in this SCC. 135 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) 136 SCCNodes.insert((*I)->getFunction()); 137 138 // Check if any of the functions in the SCC read or write memory. If they 139 // write memory then they can't be marked readnone or readonly. 140 bool ReadsMemory = false; 141 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 142 Function *F = (*I)->getFunction(); 143 144 if (F == 0) 145 // External node - may write memory. Just give up. 146 return false; 147 148 if (F->doesNotAccessMemory()) 149 // Already perfect! 150 continue; 151 152 // Definitions with weak linkage may be overridden at linktime with 153 // something that writes memory, so treat them like declarations. 154 if (F->isDeclaration() || F->mayBeOverridden()) { 155 if (!F->onlyReadsMemory()) 156 // May write memory. Just give up. 157 return false; 158 159 ReadsMemory = true; 160 continue; 161 } 162 163 // Scan the function body for instructions that may read or write memory. 164 for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) { 165 Instruction *I = &*II; 166 167 // Some instructions can be ignored even if they read or write memory. 168 // Detect these now, skipping to the next instruction if one is found. 169 CallSite CS(cast<Value>(I)); 170 if (CS && CS.getCalledFunction()) { 171 // Ignore calls to functions in the same SCC. 172 if (SCCNodes.count(CS.getCalledFunction())) 173 continue; 174 // Ignore intrinsics that only access local memory. 175 if (unsigned id = CS.getCalledFunction()->getIntrinsicID()) 176 if (AliasAnalysis::getIntrinsicModRefBehavior(id) == 177 AliasAnalysis::AccessesArguments) { 178 // Check that all pointer arguments point to local memory. 179 for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 180 CI != CE; ++CI) { 181 Value *Arg = *CI; 182 if (Arg->getType()->isPointerTy() && 183 !PointsToLocalOrConstantMemory(Arg)) 184 // Writes memory. Just give up. 185 return false; 186 } 187 // Only reads and writes local memory. 188 continue; 189 } 190 } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 191 // Ignore non-volatile loads from local memory. 192 if (!LI->isVolatile() && 193 PointsToLocalOrConstantMemory(LI->getPointerOperand())) 194 continue; 195 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 196 // Ignore non-volatile stores to local memory. 197 if (!SI->isVolatile() && 198 PointsToLocalOrConstantMemory(SI->getPointerOperand())) 199 continue; 200 } 201 202 // Any remaining instructions need to be taken seriously! Check if they 203 // read or write memory. 204 if (I->mayWriteToMemory()) 205 // Writes memory. Just give up. 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