FunctionAttrs.cpp revision 6d44d64f61359c865cbf2d7f331bb9c97ce253d5
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/LLVMContext.h" 27#include "llvm/Analysis/AliasAnalysis.h" 28#include "llvm/Analysis/CallGraph.h" 29#include "llvm/Analysis/CaptureTracking.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), AA(0) { 45 initializeFunctionAttrsPass(*PassRegistry::getPassRegistry()); 46 } 47 48 // runOnSCC - Analyze the SCC, performing the transformation if possible. 49 bool runOnSCC(CallGraphSCC &SCC); 50 51 // AddReadAttrs - Deduce readonly/readnone attributes for the SCC. 52 bool AddReadAttrs(const CallGraphSCC &SCC); 53 54 // AddNoCaptureAttrs - Deduce nocapture attributes for the SCC. 55 bool AddNoCaptureAttrs(const CallGraphSCC &SCC); 56 57 // IsFunctionMallocLike - Does this function allocate new memory? 58 bool IsFunctionMallocLike(Function *F, 59 SmallPtrSet<Function*, 8> &) const; 60 61 // AddNoAliasAttrs - Deduce noalias attributes for the SCC. 62 bool AddNoAliasAttrs(const CallGraphSCC &SCC); 63 64 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 65 AU.setPreservesCFG(); 66 AU.addRequired<AliasAnalysis>(); 67 CallGraphSCCPass::getAnalysisUsage(AU); 68 } 69 70 private: 71 AliasAnalysis *AA; 72 }; 73} 74 75char FunctionAttrs::ID = 0; 76INITIALIZE_PASS_BEGIN(FunctionAttrs, "functionattrs", 77 "Deduce function attributes", false, false) 78INITIALIZE_AG_DEPENDENCY(CallGraph) 79INITIALIZE_PASS_END(FunctionAttrs, "functionattrs", 80 "Deduce function attributes", false, false) 81 82Pass *llvm::createFunctionAttrsPass() { return new FunctionAttrs(); } 83 84 85/// AddReadAttrs - Deduce readonly/readnone attributes for the SCC. 86bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) { 87 SmallPtrSet<Function*, 8> SCCNodes; 88 89 // Fill SCCNodes with the elements of the SCC. Used for quickly 90 // looking up whether a given CallGraphNode is in this SCC. 91 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) 92 SCCNodes.insert((*I)->getFunction()); 93 94 // Check if any of the functions in the SCC read or write memory. If they 95 // write memory then they can't be marked readnone or readonly. 96 bool ReadsMemory = false; 97 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 98 Function *F = (*I)->getFunction(); 99 100 if (F == 0) 101 // External node - may write memory. Just give up. 102 return false; 103 104 AliasAnalysis::ModRefBehavior MRB = AA->getModRefBehavior(F); 105 if (MRB == AliasAnalysis::DoesNotAccessMemory) 106 // Already perfect! 107 continue; 108 109 // Definitions with weak linkage may be overridden at linktime with 110 // something that writes memory, so treat them like declarations. 111 if (F->isDeclaration() || F->mayBeOverridden()) { 112 if (!AliasAnalysis::onlyReadsMemory(MRB)) 113 // May write memory. Just give up. 114 return false; 115 116 ReadsMemory = true; 117 continue; 118 } 119 120 // Scan the function body for instructions that may read or write memory. 121 for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) { 122 Instruction *I = &*II; 123 124 // Some instructions can be ignored even if they read or write memory. 125 // Detect these now, skipping to the next instruction if one is found. 126 CallSite CS(cast<Value>(I)); 127 if (CS) { 128 // Ignore calls to functions in the same SCC. 129 if (CS.getCalledFunction() && SCCNodes.count(CS.getCalledFunction())) 130 continue; 131 switch (AA->getModRefBehavior(CS)) { 132 case AliasAnalysis::DoesNotAccessMemory: 133 // Ignore calls that don't access memory. 134 continue; 135 case AliasAnalysis::OnlyReadsMemory: 136 // Handle calls that only read from memory. 137 ReadsMemory = true; 138 continue; 139 case AliasAnalysis::AccessesArguments: 140 // Check whether all pointer arguments point to local memory, and 141 // ignore calls that only access local memory. 142 for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 143 CI != CE; ++CI) { 144 Value *Arg = *CI; 145 if (Arg->getType()->isPointerTy()) { 146 AliasAnalysis::Location Loc(Arg, 147 AliasAnalysis::UnknownSize, 148 I->getMetadata(LLVMContext::MD_tbaa)); 149 if (!AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) 150 // Writes memory. Just give up. 151 return false; 152 } 153 } 154 // Only reads and writes local memory. 155 continue; 156 case AliasAnalysis::AccessesArgumentsReadonly: 157 // Check whether all pointer arguments point to local memory, and 158 // ignore calls that only access local memory. 159 for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 160 CI != CE; ++CI) { 161 Value *Arg = *CI; 162 if (Arg->getType()->isPointerTy()) { 163 AliasAnalysis::Location Loc(Arg, 164 AliasAnalysis::UnknownSize, 165 I->getMetadata(LLVMContext::MD_tbaa)); 166 if (!AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) { 167 // Reads non-local memory. 168 ReadsMemory = true; 169 break; 170 } 171 } 172 } 173 // Only reads memory. 174 continue; 175 default: 176 // Otherwise, be conservative. 177 break; 178 } 179 } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 180 // Ignore non-volatile loads from local memory. 181 if (!LI->isVolatile()) { 182 AliasAnalysis::Location Loc(LI->getPointerOperand(), 183 AA->getTypeStoreSize(LI->getType()), 184 LI->getMetadata(LLVMContext::MD_tbaa)); 185 if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) 186 continue; 187 } 188 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 189 // Ignore non-volatile stores to local memory. 190 if (!SI->isVolatile()) { 191 const Type *StoredType = SI->getValueOperand()->getType(); 192 AliasAnalysis::Location Loc(SI->getPointerOperand(), 193 AA->getTypeStoreSize(StoredType), 194 SI->getMetadata(LLVMContext::MD_tbaa)); 195 if (AA->pointsToConstantMemory(Loc, /*OrLocal=*/true)) 196 continue; 197 } 198 } 199 200 // Any remaining instructions need to be taken seriously! Check if they 201 // read or write memory. 202 if (I->mayWriteToMemory()) 203 // Writes memory. Just give up. 204 return false; 205 206 // If this instruction may read memory, remember that. 207 ReadsMemory |= I->mayReadFromMemory(); 208 } 209 } 210 211 // Success! Functions in this SCC do not access memory, or only read memory. 212 // Give them the appropriate attribute. 213 bool MadeChange = false; 214 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 215 Function *F = (*I)->getFunction(); 216 217 if (F->doesNotAccessMemory()) 218 // Already perfect! 219 continue; 220 221 if (F->onlyReadsMemory() && ReadsMemory) 222 // No change. 223 continue; 224 225 MadeChange = true; 226 227 // Clear out any existing attributes. 228 F->removeAttribute(~0, Attribute::ReadOnly | Attribute::ReadNone); 229 230 // Add in the new attribute. 231 F->addAttribute(~0, ReadsMemory? Attribute::ReadOnly : Attribute::ReadNone); 232 233 if (ReadsMemory) 234 ++NumReadOnly; 235 else 236 ++NumReadNone; 237 } 238 239 return MadeChange; 240} 241 242/// AddNoCaptureAttrs - Deduce nocapture attributes for the SCC. 243bool FunctionAttrs::AddNoCaptureAttrs(const CallGraphSCC &SCC) { 244 bool Changed = false; 245 246 // Check each function in turn, determining which pointer arguments are not 247 // captured. 248 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 249 Function *F = (*I)->getFunction(); 250 251 if (F == 0) 252 // External node - skip it; 253 continue; 254 255 // Definitions with weak linkage may be overridden at linktime with 256 // something that writes memory, so treat them like declarations. 257 if (F->isDeclaration() || F->mayBeOverridden()) 258 continue; 259 260 for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A!=E; ++A) 261 if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr() && 262 !PointerMayBeCaptured(A, true, /*StoreCaptures=*/false)) { 263 A->addAttr(Attribute::NoCapture); 264 ++NumNoCapture; 265 Changed = true; 266 } 267 } 268 269 return Changed; 270} 271 272/// IsFunctionMallocLike - A function is malloc-like if it returns either null 273/// or a pointer that doesn't alias any other pointer visible to the caller. 274bool FunctionAttrs::IsFunctionMallocLike(Function *F, 275 SmallPtrSet<Function*, 8> &SCCNodes) const { 276 UniqueVector<Value *> FlowsToReturn; 277 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) 278 if (ReturnInst *Ret = dyn_cast<ReturnInst>(I->getTerminator())) 279 FlowsToReturn.insert(Ret->getReturnValue()); 280 281 for (unsigned i = 0; i != FlowsToReturn.size(); ++i) { 282 Value *RetVal = FlowsToReturn[i+1]; // UniqueVector[0] is reserved. 283 284 if (Constant *C = dyn_cast<Constant>(RetVal)) { 285 if (!C->isNullValue() && !isa<UndefValue>(C)) 286 return false; 287 288 continue; 289 } 290 291 if (isa<Argument>(RetVal)) 292 return false; 293 294 if (Instruction *RVI = dyn_cast<Instruction>(RetVal)) 295 switch (RVI->getOpcode()) { 296 // Extend the analysis by looking upwards. 297 case Instruction::BitCast: 298 case Instruction::GetElementPtr: 299 FlowsToReturn.insert(RVI->getOperand(0)); 300 continue; 301 case Instruction::Select: { 302 SelectInst *SI = cast<SelectInst>(RVI); 303 FlowsToReturn.insert(SI->getTrueValue()); 304 FlowsToReturn.insert(SI->getFalseValue()); 305 continue; 306 } 307 case Instruction::PHI: { 308 PHINode *PN = cast<PHINode>(RVI); 309 for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 310 FlowsToReturn.insert(PN->getIncomingValue(i)); 311 continue; 312 } 313 314 // Check whether the pointer came from an allocation. 315 case Instruction::Alloca: 316 break; 317 case Instruction::Call: 318 case Instruction::Invoke: { 319 CallSite CS(RVI); 320 if (CS.paramHasAttr(0, Attribute::NoAlias)) 321 break; 322 if (CS.getCalledFunction() && 323 SCCNodes.count(CS.getCalledFunction())) 324 break; 325 } // fall-through 326 default: 327 return false; // Did not come from an allocation. 328 } 329 330 if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false)) 331 return false; 332 } 333 334 return true; 335} 336 337/// AddNoAliasAttrs - Deduce noalias attributes for the SCC. 338bool FunctionAttrs::AddNoAliasAttrs(const CallGraphSCC &SCC) { 339 SmallPtrSet<Function*, 8> SCCNodes; 340 341 // Fill SCCNodes with the elements of the SCC. Used for quickly 342 // looking up whether a given CallGraphNode is in this SCC. 343 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) 344 SCCNodes.insert((*I)->getFunction()); 345 346 // Check each function in turn, determining which functions return noalias 347 // pointers. 348 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 349 Function *F = (*I)->getFunction(); 350 351 if (F == 0) 352 // External node - skip it; 353 return false; 354 355 // Already noalias. 356 if (F->doesNotAlias(0)) 357 continue; 358 359 // Definitions with weak linkage may be overridden at linktime, so 360 // treat them like declarations. 361 if (F->isDeclaration() || F->mayBeOverridden()) 362 return false; 363 364 // We annotate noalias return values, which are only applicable to 365 // pointer types. 366 if (!F->getReturnType()->isPointerTy()) 367 continue; 368 369 if (!IsFunctionMallocLike(F, SCCNodes)) 370 return false; 371 } 372 373 bool MadeChange = false; 374 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 375 Function *F = (*I)->getFunction(); 376 if (F->doesNotAlias(0) || !F->getReturnType()->isPointerTy()) 377 continue; 378 379 F->setDoesNotAlias(0); 380 ++NumNoAlias; 381 MadeChange = true; 382 } 383 384 return MadeChange; 385} 386 387bool FunctionAttrs::runOnSCC(CallGraphSCC &SCC) { 388 AA = &getAnalysis<AliasAnalysis>(); 389 390 bool Changed = AddReadAttrs(SCC); 391 Changed |= AddNoCaptureAttrs(SCC); 392 Changed |= AddNoAliasAttrs(SCC); 393 return Changed; 394} 395