FunctionAttrs.cpp revision b0cea8ff3979b8af15311b34df12bbb4440fd888
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/Instructions.h" 26#include "llvm/Analysis/CallGraph.h" 27#include "llvm/ADT/PointerIntPair.h" 28#include "llvm/ADT/SmallSet.h" 29#include "llvm/ADT/Statistic.h" 30#include "llvm/Support/Compiler.h" 31#include "llvm/Support/InstIterator.h" 32using namespace llvm; 33 34STATISTIC(NumReadNone, "Number of functions marked readnone"); 35STATISTIC(NumReadOnly, "Number of functions marked readonly"); 36STATISTIC(NumNoCapture, "Number of arguments marked nocapture"); 37 38namespace { 39 struct VISIBILITY_HIDDEN FunctionAttrs : public CallGraphSCCPass { 40 static char ID; // Pass identification, replacement for typeid 41 FunctionAttrs() : CallGraphSCCPass(&ID) {} 42 43 // runOnSCC - Analyze the SCC, performing the transformation if possible. 44 bool runOnSCC(const std::vector<CallGraphNode *> &SCC); 45 46 // AddReadAttrs - Deduce readonly/readnone attributes for the SCC. 47 bool AddReadAttrs(const std::vector<CallGraphNode *> &SCC); 48 49 // AddNoCaptureAttrs - Deduce nocapture attributes for the SCC. 50 bool AddNoCaptureAttrs(const std::vector<CallGraphNode *> &SCC); 51 52 // isCaptured - Return true if this pointer value may be captured. 53 bool isCaptured(Function &F, Value *V); 54 55 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 56 AU.setPreservesCFG(); 57 CallGraphSCCPass::getAnalysisUsage(AU); 58 } 59 60 bool PointsToLocalMemory(Value *V); 61 }; 62} 63 64char FunctionAttrs::ID = 0; 65static RegisterPass<FunctionAttrs> 66X("functionattrs", "Deduce function attributes"); 67 68Pass *llvm::createFunctionAttrsPass() { return new FunctionAttrs(); } 69 70 71/// PointsToLocalMemory - Returns whether the given pointer value points to 72/// memory that is local to the function. Global constants are considered 73/// local to all functions. 74bool FunctionAttrs::PointsToLocalMemory(Value *V) { 75 V = V->getUnderlyingObject(); 76 // An alloca instruction defines local memory. 77 if (isa<AllocaInst>(V)) 78 return true; 79 // A global constant counts as local memory for our purposes. 80 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) 81 return GV->isConstant(); 82 // Could look through phi nodes and selects here, but it doesn't seem 83 // to be useful in practice. 84 return false; 85} 86 87/// AddReadAttrs - Deduce readonly/readnone attributes for the SCC. 88bool FunctionAttrs::AddReadAttrs(const std::vector<CallGraphNode *> &SCC) { 89 SmallPtrSet<CallGraphNode*, 8> SCCNodes; 90 CallGraph &CG = getAnalysis<CallGraph>(); 91 92 // Fill SCCNodes with the elements of the SCC. Used for quickly 93 // looking up whether a given CallGraphNode is in this SCC. 94 for (unsigned i = 0, e = SCC.size(); i != e; ++i) 95 SCCNodes.insert(SCC[i]); 96 97 // Check if any of the functions in the SCC read or write memory. If they 98 // write memory then they can't be marked readnone or readonly. 99 bool ReadsMemory = false; 100 for (unsigned i = 0, e = SCC.size(); i != e; ++i) { 101 Function *F = SCC[i]->getFunction(); 102 103 if (F == 0) 104 // External node - may write memory. Just give up. 105 return false; 106 107 if (F->doesNotAccessMemory()) 108 // Already perfect! 109 continue; 110 111 // Definitions with weak linkage may be overridden at linktime with 112 // something that writes memory, so treat them like declarations. 113 if (F->isDeclaration() || F->mayBeOverridden()) { 114 if (!F->onlyReadsMemory()) 115 // May write memory. Just give up. 116 return false; 117 118 ReadsMemory = true; 119 continue; 120 } 121 122 // Scan the function body for instructions that may read or write memory. 123 for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) { 124 Instruction *I = &*II; 125 126 // Some instructions can be ignored even if they read or write memory. 127 // Detect these now, skipping to the next instruction if one is found. 128 CallSite CS = CallSite::get(I); 129 if (CS.getInstruction()) { 130 // Ignore calls to functions in the same SCC. 131 if (SCCNodes.count(CG[CS.getCalledFunction()])) 132 continue; 133 } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 134 // Ignore loads from local memory. 135 if (PointsToLocalMemory(LI->getPointerOperand())) 136 continue; 137 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 138 // Ignore stores to local memory. 139 if (PointsToLocalMemory(SI->getPointerOperand())) 140 continue; 141 } 142 143 // Any remaining instructions need to be taken seriously! Check if they 144 // read or write memory. 145 if (I->mayWriteToMemory()) 146 // Writes memory. Just give up. 147 return false; 148 // If this instruction may read memory, remember that. 149 ReadsMemory |= I->mayReadFromMemory(); 150 } 151 } 152 153 // Success! Functions in this SCC do not access memory, or only read memory. 154 // Give them the appropriate attribute. 155 bool MadeChange = false; 156 for (unsigned i = 0, e = SCC.size(); i != e; ++i) { 157 Function *F = SCC[i]->getFunction(); 158 159 if (F->doesNotAccessMemory()) 160 // Already perfect! 161 continue; 162 163 if (F->onlyReadsMemory() && ReadsMemory) 164 // No change. 165 continue; 166 167 MadeChange = true; 168 169 // Clear out any existing attributes. 170 F->removeAttribute(~0, Attribute::ReadOnly | Attribute::ReadNone); 171 172 // Add in the new attribute. 173 F->addAttribute(~0, ReadsMemory? Attribute::ReadOnly : Attribute::ReadNone); 174 175 if (ReadsMemory) 176 ++NumReadOnly; 177 else 178 ++NumReadNone; 179 } 180 181 return MadeChange; 182} 183 184/// isCaptured - Return true if this pointer value may be captured. 185bool FunctionAttrs::isCaptured(Function &F, Value *V) { 186 SmallVector<Use*, 16> Worklist; 187 SmallSet<Use*, 16> Visited; 188 189 for (Value::use_iterator UI = V->use_begin(), UE = V->use_end(); UI != UE; 190 ++UI) { 191 Use *U = &UI.getUse(); 192 Visited.insert(U); 193 Worklist.push_back(U); 194 } 195 196 while (!Worklist.empty()) { 197 Use *U = Worklist.pop_back_val(); 198 Instruction *I = cast<Instruction>(U->getUser()); 199 V = U->get(); 200 201 switch (I->getOpcode()) { 202 case Instruction::Call: 203 case Instruction::Invoke: { 204 CallSite CS = CallSite::get(I); 205 // Not captured if the callee is readonly and doesn't return a copy 206 // through its return value. 207 if (CS.onlyReadsMemory() && I->getType() == Type::VoidTy) 208 break; 209 210 // Not captured if only passed via 'nocapture' arguments. Note that 211 // calling a function pointer does not in itself cause the pointer to 212 // be captured. This is a subtle point considering that (for example) 213 // the callee might return its own address. It is analogous to saying 214 // that loading a value from a pointer does not cause the pointer to be 215 // captured, even though the loaded value might be the pointer itself 216 // (think of self-referential objects). 217 CallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end(); 218 for (CallSite::arg_iterator A = B; A != E; ++A) 219 if (A->get() == V && !CS.paramHasAttr(A - B + 1, Attribute::NoCapture)) 220 // The parameter is not marked 'nocapture' - captured. 221 return true; 222 // Only passed via 'nocapture' arguments, or is the called function - not 223 // captured. 224 break; 225 } 226 case Instruction::Free: 227 // Freeing a pointer does not cause it to be captured. 228 break; 229 case Instruction::Load: 230 // Loading from a pointer does not cause it to be captured. 231 break; 232 case Instruction::Store: 233 if (V == I->getOperand(0)) 234 // Stored the pointer - it may be captured. 235 return true; 236 // Storing to the pointee does not cause the pointer to be captured. 237 break; 238 case Instruction::BitCast: 239 case Instruction::GetElementPtr: 240 case Instruction::PHI: 241 case Instruction::Select: 242 // The original value is not captured via this if the new value isn't. 243 for (Instruction::use_iterator UI = I->use_begin(), UE = I->use_end(); 244 UI != UE; ++UI) { 245 Use *U = &UI.getUse(); 246 if (Visited.insert(U)) 247 Worklist.push_back(U); 248 } 249 break; 250 default: 251 // Something else - be conservative and say it is captured. 252 return true; 253 } 254 } 255 256 // All uses examined - not captured. 257 return false; 258} 259 260/// AddNoCaptureAttrs - Deduce nocapture attributes for the SCC. 261bool FunctionAttrs::AddNoCaptureAttrs(const std::vector<CallGraphNode *> &SCC) { 262 bool Changed = false; 263 264 // Check each function in turn, determining which pointer arguments are not 265 // captured. 266 for (unsigned i = 0, e = SCC.size(); i != e; ++i) { 267 Function *F = SCC[i]->getFunction(); 268 269 if (F == 0) 270 // External node - skip it; 271 continue; 272 273 // Definitions with weak linkage may be overridden at linktime with 274 // something that writes memory, so treat them like declarations. 275 if (F->isDeclaration() || F->mayBeOverridden()) 276 continue; 277 278 for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A!=E; ++A) 279 if (isa<PointerType>(A->getType()) && !A->hasNoCaptureAttr() && 280 !isCaptured(*F, A)) { 281 A->addAttr(Attribute::NoCapture); 282 ++NumNoCapture; 283 Changed = true; 284 } 285 } 286 287 return Changed; 288} 289 290bool FunctionAttrs::runOnSCC(const std::vector<CallGraphNode *> &SCC) { 291 bool Changed = AddReadAttrs(SCC); 292 Changed |= AddNoCaptureAttrs(SCC); 293 return Changed; 294} 295