LLVM API Documentation

FunctionAttrs.cpp

Go to the documentation of this file.
00001 //===- FunctionAttrs.cpp - Pass which marks functions readnone or readonly ===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file implements a simple interprocedural pass which walks the
00011 // call-graph, looking for functions which do not access or only read
00012 // non-local memory, and marking them readnone/readonly.  In addition,
00013 // it marks function arguments (of pointer type) 'nocapture' if a call
00014 // to the function does not create any copies of the pointer value that
00015 // outlive the call.  This more or less means that the pointer is only
00016 // dereferenced, and not returned from the function or stored in a global.
00017 // This pass is implemented as a bottom-up traversal of the call-graph.
00018 //
00019 //===----------------------------------------------------------------------===//
00020 
00021 #define DEBUG_TYPE "functionattrs"
00022 #include "llvm/Transforms/IPO.h"
00023 #include "llvm/CallGraphSCCPass.h"
00024 #include "llvm/GlobalVariable.h"
00025 #include "llvm/IntrinsicInst.h"
00026 #include "llvm/Analysis/AliasAnalysis.h"
00027 #include "llvm/Analysis/CallGraph.h"
00028 #include "llvm/Analysis/CaptureTracking.h"
00029 #include "llvm/ADT/SmallSet.h"
00030 #include "llvm/ADT/Statistic.h"
00031 #include "llvm/ADT/UniqueVector.h"
00032 #include "llvm/Support/Compiler.h"
00033 #include "llvm/Support/InstIterator.h"
00034 using namespace llvm;
00035 
00036 STATISTIC(NumReadNone, "Number of functions marked readnone");
00037 STATISTIC(NumReadOnly, "Number of functions marked readonly");
00038 STATISTIC(NumNoCapture, "Number of arguments marked nocapture");
00039 STATISTIC(NumNoAlias, "Number of function returns marked noalias");
00040 
00041 namespace {
00042   struct VISIBILITY_HIDDEN FunctionAttrs : public CallGraphSCCPass {
00043     static char ID; // Pass identification, replacement for typeid
00044     FunctionAttrs() : CallGraphSCCPass(&ID) {}
00045 
00046     // runOnSCC - Analyze the SCC, performing the transformation if possible.
00047     bool runOnSCC(const std::vector<CallGraphNode *> &SCC);
00048 
00049     // AddReadAttrs - Deduce readonly/readnone attributes for the SCC.
00050     bool AddReadAttrs(const std::vector<CallGraphNode *> &SCC);
00051 
00052     // AddNoCaptureAttrs - Deduce nocapture attributes for the SCC.
00053     bool AddNoCaptureAttrs(const std::vector<CallGraphNode *> &SCC);
00054 
00055     // IsFunctionMallocLike - Does this function allocate new memory?
00056     bool IsFunctionMallocLike(Function *F,
00057                               SmallPtrSet<CallGraphNode*, 8> &) const;
00058 
00059     // AddNoAliasAttrs - Deduce noalias attributes for the SCC.
00060     bool AddNoAliasAttrs(const std::vector<CallGraphNode *> &SCC);
00061 
00062     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00063       AU.setPreservesCFG();
00064       CallGraphSCCPass::getAnalysisUsage(AU);
00065     }
00066 
00067     bool PointsToLocalMemory(Value *V);
00068   };
00069 }
00070 
00071 char FunctionAttrs::ID = 0;
00072 static RegisterPass<FunctionAttrs>
00073 X("functionattrs", "Deduce function attributes");
00074 
00075 Pass *llvm::createFunctionAttrsPass() { return new FunctionAttrs(); }
00076 
00077 
00078 /// PointsToLocalMemory - Returns whether the given pointer value points to
00079 /// memory that is local to the function.  Global constants are considered
00080 /// local to all functions.
00081 bool FunctionAttrs::PointsToLocalMemory(Value *V) {
00082   V = V->getUnderlyingObject();
00083   // An alloca instruction defines local memory.
00084   if (isa<AllocaInst>(V))
00085     return true;
00086   // A global constant counts as local memory for our purposes.
00087   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
00088     return GV->isConstant();
00089   // Could look through phi nodes and selects here, but it doesn't seem
00090   // to be useful in practice.
00091   return false;
00092 }
00093 
00094 /// AddReadAttrs - Deduce readonly/readnone attributes for the SCC.
00095 bool FunctionAttrs::AddReadAttrs(const std::vector<CallGraphNode *> &SCC) {
00096   SmallPtrSet<CallGraphNode*, 8> SCCNodes;
00097   CallGraph &CG = getAnalysis<CallGraph>();
00098 
00099   // Fill SCCNodes with the elements of the SCC.  Used for quickly
00100   // looking up whether a given CallGraphNode is in this SCC.
00101   for (unsigned i = 0, e = SCC.size(); i != e; ++i)
00102     SCCNodes.insert(SCC[i]);
00103 
00104   // Check if any of the functions in the SCC read or write memory.  If they
00105   // write memory then they can't be marked readnone or readonly.
00106   bool ReadsMemory = false;
00107   for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
00108     Function *F = SCC[i]->getFunction();
00109 
00110     if (F == 0)
00111       // External node - may write memory.  Just give up.
00112       return false;
00113 
00114     if (F->doesNotAccessMemory())
00115       // Already perfect!
00116       continue;
00117 
00118     // Definitions with weak linkage may be overridden at linktime with
00119     // something that writes memory, so treat them like declarations.
00120     if (F->isDeclaration() || F->mayBeOverridden()) {
00121       if (!F->onlyReadsMemory())
00122         // May write memory.  Just give up.
00123         return false;
00124 
00125       ReadsMemory = true;
00126       continue;
00127     }
00128 
00129     // Scan the function body for instructions that may read or write memory.
00130     for (inst_iterator II = inst_begin(F), E = inst_end(F); II != E; ++II) {
00131       Instruction *I = &*II;
00132 
00133       // Some instructions can be ignored even if they read or write memory.
00134       // Detect these now, skipping to the next instruction if one is found.
00135       CallSite CS = CallSite::get(I);
00136       if (CS.getInstruction()) {
00137         // Ignore calls to functions in the same SCC.
00138         if (SCCNodes.count(CG[CS.getCalledFunction()]))
00139           continue;
00140       } else if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
00141         // Ignore loads from local memory.
00142         if (PointsToLocalMemory(LI->getPointerOperand()))
00143           continue;
00144       } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
00145         // Ignore stores to local memory.
00146         if (PointsToLocalMemory(SI->getPointerOperand()))
00147           continue;
00148       }
00149 
00150       // Any remaining instructions need to be taken seriously!  Check if they
00151       // read or write memory.
00152       if (I->mayWriteToMemory())
00153         // Writes memory.  Just give up.
00154         return false;
00155 
00156       if (isa<MallocInst>(I))
00157         // MallocInst claims not to write memory!  PR3754.
00158         return false;
00159 
00160       // If this instruction may read memory, remember that.
00161       ReadsMemory |= I->mayReadFromMemory();
00162     }
00163   }
00164 
00165   // Success!  Functions in this SCC do not access memory, or only read memory.
00166   // Give them the appropriate attribute.
00167   bool MadeChange = false;
00168   for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
00169     Function *F = SCC[i]->getFunction();
00170 
00171     if (F->doesNotAccessMemory())
00172       // Already perfect!
00173       continue;
00174 
00175     if (F->onlyReadsMemory() && ReadsMemory)
00176       // No change.
00177       continue;
00178 
00179     MadeChange = true;
00180 
00181     // Clear out any existing attributes.
00182     F->removeAttribute(~0, Attribute::ReadOnly | Attribute::ReadNone);
00183 
00184     // Add in the new attribute.
00185     F->addAttribute(~0, ReadsMemory? Attribute::ReadOnly : Attribute::ReadNone);
00186 
00187     if (ReadsMemory)
00188       ++NumReadOnly;
00189     else
00190       ++NumReadNone;
00191   }
00192 
00193   return MadeChange;
00194 }
00195 
00196 /// AddNoCaptureAttrs - Deduce nocapture attributes for the SCC.
00197 bool FunctionAttrs::AddNoCaptureAttrs(const std::vector<CallGraphNode *> &SCC) {
00198   bool Changed = false;
00199 
00200   // Check each function in turn, determining which pointer arguments are not
00201   // captured.
00202   for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
00203     Function *F = SCC[i]->getFunction();
00204 
00205     if (F == 0)
00206       // External node - skip it;
00207       continue;
00208 
00209     // Definitions with weak linkage may be overridden at linktime with
00210     // something that writes memory, so treat them like declarations.
00211     if (F->isDeclaration() || F->mayBeOverridden())
00212       continue;
00213 
00214     for (Function::arg_iterator A = F->arg_begin(), E = F->arg_end(); A!=E; ++A)
00215       if (isa<PointerType>(A->getType()) && !A->hasNoCaptureAttr() &&
00216           !PointerMayBeCaptured(A, true)) {
00217         A->addAttr(Attribute::NoCapture);
00218         ++NumNoCapture;
00219         Changed = true;
00220       }
00221   }
00222 
00223   return Changed;
00224 }
00225 
00226 /// IsFunctionMallocLike - A function is malloc-like if it returns either null
00227 /// or a pointer that doesn't alias any other pointer visible to the caller.
00228 bool FunctionAttrs::IsFunctionMallocLike(Function *F,
00229                               SmallPtrSet<CallGraphNode*, 8> &SCCNodes) const {
00230   CallGraph &CG = getAnalysis<CallGraph>();
00231 
00232   UniqueVector<Value *> FlowsToReturn;
00233   for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
00234     if (ReturnInst *Ret = dyn_cast<ReturnInst>(I->getTerminator()))
00235       FlowsToReturn.insert(Ret->getReturnValue());
00236 
00237   for (unsigned i = 0; i != FlowsToReturn.size(); ++i) {
00238     Value *RetVal = FlowsToReturn[i+1];   // UniqueVector[0] is reserved.
00239 
00240     if (Constant *C = dyn_cast<Constant>(RetVal)) {
00241       if (!C->isNullValue() && !isa<UndefValue>(C))
00242         return false;
00243 
00244       continue;
00245     }
00246 
00247     if (isa<Argument>(RetVal))
00248       return false;
00249 
00250     if (Instruction *RVI = dyn_cast<Instruction>(RetVal))
00251       switch (RVI->getOpcode()) {
00252         // Extend the analysis by looking upwards.
00253         case Instruction::GetElementPtr:
00254         case Instruction::BitCast:
00255           FlowsToReturn.insert(RVI->getOperand(0));
00256           continue;
00257         case Instruction::Select: {
00258           SelectInst *SI = cast<SelectInst>(RVI);
00259           FlowsToReturn.insert(SI->getTrueValue());
00260           FlowsToReturn.insert(SI->getFalseValue());
00261         } continue;
00262         case Instruction::PHI: {
00263           PHINode *PN = cast<PHINode>(RVI);
00264           for (int i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
00265             FlowsToReturn.insert(PN->getIncomingValue(i));
00266         } continue;
00267 
00268         // Check whether the pointer came from an allocation.
00269         case Instruction::Alloca:
00270         case Instruction::Malloc:
00271           break;
00272         case Instruction::Call:
00273         case Instruction::Invoke: {
00274           CallSite CS(RVI);
00275           if (CS.paramHasAttr(0, Attribute::NoAlias))
00276             break;
00277           if (CS.getCalledFunction() &&
00278               SCCNodes.count(CG[CS.getCalledFunction()]))
00279             break;
00280         } // fall-through
00281         default:
00282           return false;  // Did not come from an allocation.
00283       }
00284 
00285     if (PointerMayBeCaptured(RetVal, false))
00286       return false;
00287   }
00288 
00289   return true;
00290 }
00291 
00292 /// AddNoAliasAttrs - Deduce noalias attributes for the SCC.
00293 bool FunctionAttrs::AddNoAliasAttrs(const std::vector<CallGraphNode *> &SCC) {
00294   SmallPtrSet<CallGraphNode*, 8> SCCNodes;
00295 
00296   // Fill SCCNodes with the elements of the SCC.  Used for quickly
00297   // looking up whether a given CallGraphNode is in this SCC.
00298   for (unsigned i = 0, e = SCC.size(); i != e; ++i)
00299     SCCNodes.insert(SCC[i]);
00300 
00301   // Check each function in turn, determining which functions return noalias
00302   // pointers.
00303   for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
00304     Function *F = SCC[i]->getFunction();
00305 
00306     if (F == 0)
00307       // External node - skip it;
00308       return false;
00309 
00310     // Already noalias.
00311     if (F->doesNotAlias(0))
00312       continue;
00313 
00314     // Definitions with weak linkage may be overridden at linktime, so
00315     // treat them like declarations.
00316     if (F->isDeclaration() || F->mayBeOverridden())
00317       return false;
00318 
00319     // We annotate noalias return values, which are only applicable to 
00320     // pointer types.
00321     if (!isa<PointerType>(F->getReturnType()))
00322       continue;
00323 
00324     if (!IsFunctionMallocLike(F, SCCNodes))
00325       return false;
00326   }
00327 
00328   bool MadeChange = false;
00329   for (unsigned i = 0, e = SCC.size(); i != e; ++i) {
00330     Function *F = SCC[i]->getFunction();
00331     if (F->doesNotAlias(0) || !isa<PointerType>(F->getReturnType()))
00332       continue;
00333 
00334     F->setDoesNotAlias(0);
00335     ++NumNoAlias;
00336     MadeChange = true;
00337   }
00338 
00339   return MadeChange;
00340 }
00341 
00342 bool FunctionAttrs::runOnSCC(const std::vector<CallGraphNode *> &SCC) {
00343   bool Changed = AddReadAttrs(SCC);
00344   Changed |= AddNoCaptureAttrs(SCC);
00345   Changed |= AddNoAliasAttrs(SCC);
00346   return Changed;
00347 }