lib/Transforms/IPO/FunctionAttrs.cpp

   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"
  32 using namespace llvm;
  33
  34 STATISTIC(NumReadNone, "Number of functions marked readnone");
  35 STATISTIC(NumReadOnly, "Number of functions marked readonly");
  36 STATISTIC(NumNoCapture, "Number of arguments marked nocapture");
  37
  38 namespace {
  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
  61 char FunctionAttrs::ID = 0;
  62 static RegisterPass<FunctionAttrs>
  63 X("functionattrs", "Deduce function attributes");
  64
  65 Pass *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.
  71 bool 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.
  85 bool 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.
 186 bool 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
 215 bool FunctionAttrs::runOnSCC(const std::vector<CallGraphNode *> &SCC) {
 216   bool Changed = AddReadAttrs(SCC);
 217   Changed |= AddNoCaptureAttrs(SCC);
 218   return Changed;
 219 }