FunctionAttrs.cpp revision 711b384f7df3e41e708a89a49da00da2974a9d0e
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/CallGraph.h" 27#include "llvm/Analysis/CaptureTracking.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 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 53 AU.setPreservesCFG(); 54 CallGraphSCCPass::getAnalysisUsage(AU); 55 } 56 57 bool PointsToLocalMemory(Value *V); 58 }; 59} 60 61char FunctionAttrs::ID = 0; 62static RegisterPass<FunctionAttrs> 63X("functionattrs", "Deduce function attributes"); 64 65Pass *llvm::createFunctionAttrsPass() { return new FunctionAttrs(); } 66 67 68/// PointsToLocalMemory - Returns whether the given pointer value points to 69/// memory that is local to the function. Global constants are considered 70/// local to all functions. 71bool FunctionAttrs::PointsToLocalMemory(Value *V) { 72 V = V->getUnderlyingObject(); 73 // An alloca instruction defines local memory. 74 if (isa<AllocaInst>(V)) 75 return true; 76 // A global constant counts as local memory for our purposes. 77 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) 78 return GV->isConstant(); 79 // Could look through phi nodes and selects here, but it doesn't seem 80 // to be useful in practice. 81 return false; 82} 83 84/// AddReadAttrs - Deduce readonly/readnone attributes for the SCC. 85bool FunctionAttrs::AddReadAttrs(const std::vector<CallGraphNode *> &SCC) { 86 SmallPtrSet<CallGraphNode*, 8> SCCNodes; 87 CallGraph &CG = getAnalysis<CallGraph>(); 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 (unsigned i = 0, e = SCC.size(); i != e; ++i) 92 SCCNodes.insert(SCC[i]); 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 (unsigned i = 0, e = SCC.size(); i != e; ++i) { 98 Function *F = SCC[i]->getFunction(); 99 100 if (F == 0) 101 // External node - may write memory. Just give up. 102 return false; 103 104 if (F->doesNotAccessMemory()) 105 // Already perfect! 106 continue; 107 108 // Definitions with weak linkage may be overridden at linktime with 109 // something that writes memory, so treat them like declarations. 110 if (F->isDeclaration() || F->mayBeOverridden()) { 111 if (!F->onlyReadsMemory()) 112 // May write memory. Just give up. 113 return false; 114 115 ReadsMemory = true; 116 continue; 117 } 118 119 // Scan the function body for instructions that may read or write memory. 120 for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) { 121 Instruction *I = &*II; 122 123 // Some instructions can be ignored even if they read or write memory. 124 // Detect these now, skipping to the next instruction if one is found. 125 CallSite CS = CallSite::get(I); 126 if (CS.getInstruction()) { 127 // Ignore calls to functions in the same SCC. 128 if (SCCNodes.count(CG[CS.getCalledFunction()])) 129 continue; 130 } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) { 131 // Ignore loads from local memory. 132 if (PointsToLocalMemory(LI->getPointerOperand())) 133 continue; 134 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) { 135 // Ignore stores to local memory. 136 if (PointsToLocalMemory(SI->getPointerOperand())) 137 continue; 138 } 139 140 // Ignore dbg info intrinsics. 141 if (isa<DbgInfoIntrinsic>(I)) 142 continue; 143 144 // Any remaining instructions need to be taken seriously! Check if they 145 // read or write memory. 146 if (I->mayWriteToMemory()) 147 // Writes memory. Just give up. 148 return false; 149 // If this instruction may read memory, remember that. 150 ReadsMemory |= I->mayReadFromMemory(); 151 } 152 } 153 154 // Success! Functions in this SCC do not access memory, or only read memory. 155 // Give them the appropriate attribute. 156 bool MadeChange = false; 157 for (unsigned i = 0, e = SCC.size(); i != e; ++i) { 158 Function *F = SCC[i]->getFunction(); 159 160 if (F->doesNotAccessMemory()) 161 // Already perfect! 162 continue; 163 164 if (F->onlyReadsMemory() && ReadsMemory) 165 // No change. 166 continue; 167 168 MadeChange = true; 169 170 // Clear out any existing attributes. 171 F->removeAttribute(~0, Attribute::ReadOnly | Attribute::ReadNone); 172 173 // Add in the new attribute. 174 F->addAttribute(~0, ReadsMemory? Attribute::ReadOnly : Attribute::ReadNone); 175 176 if (ReadsMemory) 177 ++NumReadOnly; 178 else 179 ++NumReadNone; 180 } 181 182 return MadeChange; 183} 184 185/// AddNoCaptureAttrs - Deduce nocapture attributes for the SCC. 186bool FunctionAttrs::AddNoCaptureAttrs(const std::vector<CallGraphNode *> &SCC) { 187 bool Changed = false; 188 189 // Check each function in turn, determining which pointer arguments are not 190 // captured. 191 for (unsigned i = 0, e = SCC.size(); i != e; ++i) { 192 Function *F = SCC[i]->getFunction(); 193 194 if (F == 0) 195 // External node - skip it; 196 continue; 197 198 // Definitions with weak linkage may be overridden at linktime with 199 // something that writes memory, so treat them like declarations. 200 if (F->isDeclaration() || F->mayBeOverridden()) 201 continue; 202 203 for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A!=E; ++A) 204 if (isa<PointerType>(A->getType()) && !A->hasNoCaptureAttr() && 205 !PointerMayBeCaptured(A, true)) { 206 A->addAttr(Attribute::NoCapture); 207 ++NumNoCapture; 208 Changed = true; 209 } 210 } 211 212 return Changed; 213} 214 215bool FunctionAttrs::runOnSCC(const std::vector<CallGraphNode *> &SCC) { 216 bool Changed = AddReadAttrs(SCC); 217 Changed |= AddNoCaptureAttrs(SCC); 218 return Changed; 219} 220