FunctionAttrs.cpp revision 331003c6d9cc86490a066d74314a67058da2e5d4
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 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 CallGraphSCCPass::getAnalysisUsage(AU); 67 } 68 69 bool PointsToLocalMemory(Value *V); 70 }; 71} 72 73char FunctionAttrs::ID = 0; 74INITIALIZE_PASS_BEGIN(FunctionAttrs, "functionattrs", 75 "Deduce function attributes", false, false) 76INITIALIZE_AG_DEPENDENCY(CallGraph) 77INITIALIZE_PASS_END(FunctionAttrs, "functionattrs", 78 "Deduce function attributes", false, false) 79 80Pass *llvm::createFunctionAttrsPass() { return new FunctionAttrs(); } 81 82 83/// PointsToLocalMemory - Returns whether the given pointer value points to 84/// memory that is local to the function. Global constants are considered 85/// local to all functions. 86bool FunctionAttrs::PointsToLocalMemory(Value *V) { 87 SmallVector<Value*, 16> Worklist; 88 unsigned MaxLookup = 8; 89 90 Worklist.push_back(V); 91 92 do { 93 V = Worklist.pop_back_val()->getUnderlyingObject(); 94 95 // An alloca instruction defines local memory. 96 if (isa<AllocaInst>(V)) 97 continue; 98 99 // A global constant counts as local memory for our purposes. 100 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) { 101 if (!GV->isConstant()) 102 return false; 103 continue; 104 } 105 106 // If both select values point to local memory, then so does the select. 107 if (SelectInst *SI = dyn_cast<SelectInst>(V)) { 108 Worklist.push_back(SI->getTrueValue()); 109 Worklist.push_back(SI->getFalseValue()); 110 continue; 111 } 112 113 // If all values incoming to a phi node point to local memory, then so does 114 // the phi. 115 if (PHINode *PN = dyn_cast<PHINode>(V)) { 116 // Don't bother inspecting phi nodes with many operands. 117 if (PN->getNumIncomingValues() > MaxLookup) 118 return false; 119 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 120 Worklist.push_back(PN->getIncomingValue(i)); 121 continue; 122 } 123 124 return false; 125 } while (!Worklist.empty() && --MaxLookup); 126 127 return Worklist.empty(); 128} 129 130/// AddReadAttrs - Deduce readonly/readnone attributes for the SCC. 131bool FunctionAttrs::AddReadAttrs(const CallGraphSCC &SCC) { 132 SmallPtrSet<Function*, 8> SCCNodes; 133 134 // Fill SCCNodes with the elements of the SCC. Used for quickly 135 // looking up whether a given CallGraphNode is in this SCC. 136 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) 137 SCCNodes.insert((*I)->getFunction()); 138 139 // Check if any of the functions in the SCC read or write memory. If they 140 // write memory then they can't be marked readnone or readonly. 141 bool ReadsMemory = false; 142 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 143 Function *F = (*I)->getFunction(); 144 145 if (F == 0) 146 // External node - may write memory. Just give up. 147 return false; 148 149 if (F->doesNotAccessMemory()) 150 // Already perfect! 151 continue; 152 153 // Definitions with weak linkage may be overridden at linktime with 154 // something that writes memory, so treat them like declarations. 155 if (F->isDeclaration() || F->mayBeOverridden()) { 156 if (!F->onlyReadsMemory()) 157 // May write memory. Just give up. 158 return false; 159 160 ReadsMemory = true; 161 continue; 162 } 163 164 // Scan the function body for instructions that may read or write memory. 165 for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) { 166 Instruction *I = &*II; 167 168 // Some instructions can be ignored even if they read or write memory. 169 // Detect these now, skipping to the next instruction if one is found. 170 CallSite CS(cast<Value>(I)); 171 if (CS && CS.getCalledFunction()) { 172 // Ignore calls to functions in the same SCC. 173 if (SCCNodes.count(CS.getCalledFunction())) 174 continue; 175 // Ignore intrinsics that only access local memory. 176 if (unsigned id = CS.getCalledFunction()->getIntrinsicID()) 177 if (AliasAnalysis::getIntrinsicModRefBehavior(id) == 178 AliasAnalysis::AccessesArguments) { 179 // Check that all pointer arguments point to local memory. 180 for (CallSite::arg_iterator CI = CS.arg_begin(), CE = CS.arg_end(); 181 CI != CE; ++CI) { 182 Value *Arg = *CI; 183 if (Arg->getType()->isPointerTy() && !PointsToLocalMemory(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() && PointsToLocalMemory(LI->getPointerOperand())) 193 continue; 194 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 195 // Ignore non-volatile stores to local memory. 196 if (!SI->isVolatile() && PointsToLocalMemory(SI->getPointerOperand())) 197 continue; 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 (isMalloc(I)) 207 // malloc claims not to write memory! PR3754. 208 return false; 209 210 // If this instruction may read memory, remember that. 211 ReadsMemory |= I->mayReadFromMemory(); 212 } 213 } 214 215 // Success! Functions in this SCC do not access memory, or only read memory. 216 // Give them the appropriate attribute. 217 bool MadeChange = false; 218 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 219 Function *F = (*I)->getFunction(); 220 221 if (F->doesNotAccessMemory()) 222 // Already perfect! 223 continue; 224 225 if (F->onlyReadsMemory() && ReadsMemory) 226 // No change. 227 continue; 228 229 MadeChange = true; 230 231 // Clear out any existing attributes. 232 F->removeAttribute(~0, Attribute::ReadOnly | Attribute::ReadNone); 233 234 // Add in the new attribute. 235 F->addAttribute(~0, ReadsMemory? Attribute::ReadOnly : Attribute::ReadNone); 236 237 if (ReadsMemory) 238 ++NumReadOnly; 239 else 240 ++NumReadNone; 241 } 242 243 return MadeChange; 244} 245 246/// AddNoCaptureAttrs - Deduce nocapture attributes for the SCC. 247bool FunctionAttrs::AddNoCaptureAttrs(const CallGraphSCC &SCC) { 248 bool Changed = false; 249 250 // Check each function in turn, determining which pointer arguments are not 251 // captured. 252 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 253 Function *F = (*I)->getFunction(); 254 255 if (F == 0) 256 // External node - skip it; 257 continue; 258 259 // Definitions with weak linkage may be overridden at linktime with 260 // something that writes memory, so treat them like declarations. 261 if (F->isDeclaration() || F->mayBeOverridden()) 262 continue; 263 264 for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A!=E; ++A) 265 if (A->getType()->isPointerTy() && !A->hasNoCaptureAttr() && 266 !PointerMayBeCaptured(A, true, /*StoreCaptures=*/false)) { 267 A->addAttr(Attribute::NoCapture); 268 ++NumNoCapture; 269 Changed = true; 270 } 271 } 272 273 return Changed; 274} 275 276/// IsFunctionMallocLike - A function is malloc-like if it returns either null 277/// or a pointer that doesn't alias any other pointer visible to the caller. 278bool FunctionAttrs::IsFunctionMallocLike(Function *F, 279 SmallPtrSet<Function*, 8> &SCCNodes) const { 280 UniqueVector<Value *> FlowsToReturn; 281 for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I) 282 if (ReturnInst *Ret = dyn_cast<ReturnInst>(I->getTerminator())) 283 FlowsToReturn.insert(Ret->getReturnValue()); 284 285 for (unsigned i = 0; i != FlowsToReturn.size(); ++i) { 286 Value *RetVal = FlowsToReturn[i+1]; // UniqueVector[0] is reserved. 287 288 if (Constant *C = dyn_cast<Constant>(RetVal)) { 289 if (!C->isNullValue() && !isa<UndefValue>(C)) 290 return false; 291 292 continue; 293 } 294 295 if (isa<Argument>(RetVal)) 296 return false; 297 298 if (Instruction *RVI = dyn_cast<Instruction>(RetVal)) 299 switch (RVI->getOpcode()) { 300 // Extend the analysis by looking upwards. 301 case Instruction::BitCast: 302 case Instruction::GetElementPtr: 303 FlowsToReturn.insert(RVI->getOperand(0)); 304 continue; 305 case Instruction::Select: { 306 SelectInst *SI = cast<SelectInst>(RVI); 307 FlowsToReturn.insert(SI->getTrueValue()); 308 FlowsToReturn.insert(SI->getFalseValue()); 309 continue; 310 } 311 case Instruction::PHI: { 312 PHINode *PN = cast<PHINode>(RVI); 313 for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 314 FlowsToReturn.insert(PN->getIncomingValue(i)); 315 continue; 316 } 317 318 // Check whether the pointer came from an allocation. 319 case Instruction::Alloca: 320 break; 321 case Instruction::Call: 322 case Instruction::Invoke: { 323 CallSite CS(RVI); 324 if (CS.paramHasAttr(0, Attribute::NoAlias)) 325 break; 326 if (CS.getCalledFunction() && 327 SCCNodes.count(CS.getCalledFunction())) 328 break; 329 } // fall-through 330 default: 331 return false; // Did not come from an allocation. 332 } 333 334 if (PointerMayBeCaptured(RetVal, false, /*StoreCaptures=*/false)) 335 return false; 336 } 337 338 return true; 339} 340 341/// AddNoAliasAttrs - Deduce noalias attributes for the SCC. 342bool FunctionAttrs::AddNoAliasAttrs(const CallGraphSCC &SCC) { 343 SmallPtrSet<Function*, 8> SCCNodes; 344 345 // Fill SCCNodes with the elements of the SCC. Used for quickly 346 // looking up whether a given CallGraphNode is in this SCC. 347 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) 348 SCCNodes.insert((*I)->getFunction()); 349 350 // Check each function in turn, determining which functions return noalias 351 // pointers. 352 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 353 Function *F = (*I)->getFunction(); 354 355 if (F == 0) 356 // External node - skip it; 357 return false; 358 359 // Already noalias. 360 if (F->doesNotAlias(0)) 361 continue; 362 363 // Definitions with weak linkage may be overridden at linktime, so 364 // treat them like declarations. 365 if (F->isDeclaration() || F->mayBeOverridden()) 366 return false; 367 368 // We annotate noalias return values, which are only applicable to 369 // pointer types. 370 if (!F->getReturnType()->isPointerTy()) 371 continue; 372 373 if (!IsFunctionMallocLike(F, SCCNodes)) 374 return false; 375 } 376 377 bool MadeChange = false; 378 for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) { 379 Function *F = (*I)->getFunction(); 380 if (F->doesNotAlias(0) || !F->getReturnType()->isPointerTy()) 381 continue; 382 383 F->setDoesNotAlias(0); 384 ++NumNoAlias; 385 MadeChange = true; 386 } 387 388 return MadeChange; 389} 390 391bool FunctionAttrs::runOnSCC(CallGraphSCC &SCC) { 392 bool Changed = AddReadAttrs(SCC); 393 Changed |= AddNoCaptureAttrs(SCC); 394 Changed |= AddNoAliasAttrs(SCC); 395 return Changed; 396} 397