LLVM  mainline
ProvenanceAnalysis.cpp
Go to the documentation of this file.
00001 //===- ProvenanceAnalysis.cpp - ObjC ARC Optimization ---------------------===//
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 /// \file
00010 ///
00011 /// This file defines a special form of Alias Analysis called ``Provenance
00012 /// Analysis''. The word ``provenance'' refers to the history of the ownership
00013 /// of an object. Thus ``Provenance Analysis'' is an analysis which attempts to
00014 /// use various techniques to determine if locally
00015 ///
00016 /// WARNING: This file knows about certain library functions. It recognizes them
00017 /// by name, and hardwires knowledge of their semantics.
00018 ///
00019 /// WARNING: This file knows about how certain Objective-C library functions are
00020 /// used. Naive LLVM IR transformations which would otherwise be
00021 /// behavior-preserving may break these assumptions.
00022 ///
00023 //===----------------------------------------------------------------------===//
00024 
00025 #include "ObjCARC.h"
00026 #include "ProvenanceAnalysis.h"
00027 #include "llvm/ADT/STLExtras.h"
00028 #include "llvm/ADT/SmallPtrSet.h"
00029 
00030 using namespace llvm;
00031 using namespace llvm::objcarc;
00032 
00033 bool ProvenanceAnalysis::relatedSelect(const SelectInst *A,
00034                                        const Value *B) {
00035   const DataLayout &DL = A->getModule()->getDataLayout();
00036   // If the values are Selects with the same condition, we can do a more precise
00037   // check: just check for relations between the values on corresponding arms.
00038   if (const SelectInst *SB = dyn_cast<SelectInst>(B))
00039     if (A->getCondition() == SB->getCondition())
00040       return related(A->getTrueValue(), SB->getTrueValue(), DL) ||
00041              related(A->getFalseValue(), SB->getFalseValue(), DL);
00042 
00043   // Check both arms of the Select node individually.
00044   return related(A->getTrueValue(), B, DL) ||
00045          related(A->getFalseValue(), B, DL);
00046 }
00047 
00048 bool ProvenanceAnalysis::relatedPHI(const PHINode *A,
00049                                     const Value *B) {
00050   const DataLayout &DL = A->getModule()->getDataLayout();
00051   // If the values are PHIs in the same block, we can do a more precise as well
00052   // as efficient check: just check for relations between the values on
00053   // corresponding edges.
00054   if (const PHINode *PNB = dyn_cast<PHINode>(B))
00055     if (PNB->getParent() == A->getParent()) {
00056       for (unsigned i = 0, e = A->getNumIncomingValues(); i != e; ++i)
00057         if (related(A->getIncomingValue(i),
00058                     PNB->getIncomingValueForBlock(A->getIncomingBlock(i)), DL))
00059           return true;
00060       return false;
00061     }
00062 
00063   // Check each unique source of the PHI node against B.
00064   SmallPtrSet<const Value *, 4> UniqueSrc;
00065   for (unsigned i = 0, e = A->getNumIncomingValues(); i != e; ++i) {
00066     const Value *PV1 = A->getIncomingValue(i);
00067     if (UniqueSrc.insert(PV1).second && related(PV1, B, DL))
00068       return true;
00069   }
00070 
00071   // All of the arms checked out.
00072   return false;
00073 }
00074 
00075 /// Test if the value of P, or any value covered by its provenance, is ever
00076 /// stored within the function (not counting callees).
00077 static bool IsStoredObjCPointer(const Value *P) {
00078   SmallPtrSet<const Value *, 8> Visited;
00079   SmallVector<const Value *, 8> Worklist;
00080   Worklist.push_back(P);
00081   Visited.insert(P);
00082   do {
00083     P = Worklist.pop_back_val();
00084     for (const Use &U : P->uses()) {
00085       const User *Ur = U.getUser();
00086       if (isa<StoreInst>(Ur)) {
00087         if (U.getOperandNo() == 0)
00088           // The pointer is stored.
00089           return true;
00090         // The pointed is stored through.
00091         continue;
00092       }
00093       if (isa<CallInst>(Ur))
00094         // The pointer is passed as an argument, ignore this.
00095         continue;
00096       if (isa<PtrToIntInst>(P))
00097         // Assume the worst.
00098         return true;
00099       if (Visited.insert(Ur).second)
00100         Worklist.push_back(Ur);
00101     }
00102   } while (!Worklist.empty());
00103 
00104   // Everything checked out.
00105   return false;
00106 }
00107 
00108 bool ProvenanceAnalysis::relatedCheck(const Value *A, const Value *B,
00109                                       const DataLayout &DL) {
00110   // Skip past provenance pass-throughs.
00111   A = GetUnderlyingObjCPtr(A, DL);
00112   B = GetUnderlyingObjCPtr(B, DL);
00113 
00114   // Quick check.
00115   if (A == B)
00116     return true;
00117 
00118   // Ask regular AliasAnalysis, for a first approximation.
00119   switch (AA->alias(A, B)) {
00120   case AliasAnalysis::NoAlias:
00121     return false;
00122   case AliasAnalysis::MustAlias:
00123   case AliasAnalysis::PartialAlias:
00124     return true;
00125   case AliasAnalysis::MayAlias:
00126     break;
00127   }
00128 
00129   bool AIsIdentified = IsObjCIdentifiedObject(A);
00130   bool BIsIdentified = IsObjCIdentifiedObject(B);
00131 
00132   // An ObjC-Identified object can't alias a load if it is never locally stored.
00133   if (AIsIdentified) {
00134     // Check for an obvious escape.
00135     if (isa<LoadInst>(B))
00136       return IsStoredObjCPointer(A);
00137     if (BIsIdentified) {
00138       // Check for an obvious escape.
00139       if (isa<LoadInst>(A))
00140         return IsStoredObjCPointer(B);
00141       // Both pointers are identified and escapes aren't an evident problem.
00142       return false;
00143     }
00144   } else if (BIsIdentified) {
00145     // Check for an obvious escape.
00146     if (isa<LoadInst>(A))
00147       return IsStoredObjCPointer(B);
00148   }
00149 
00150    // Special handling for PHI and Select.
00151   if (const PHINode *PN = dyn_cast<PHINode>(A))
00152     return relatedPHI(PN, B);
00153   if (const PHINode *PN = dyn_cast<PHINode>(B))
00154     return relatedPHI(PN, A);
00155   if (const SelectInst *S = dyn_cast<SelectInst>(A))
00156     return relatedSelect(S, B);
00157   if (const SelectInst *S = dyn_cast<SelectInst>(B))
00158     return relatedSelect(S, A);
00159 
00160   // Conservative.
00161   return true;
00162 }
00163 
00164 bool ProvenanceAnalysis::related(const Value *A, const Value *B,
00165                                  const DataLayout &DL) {
00166   // Begin by inserting a conservative value into the map. If the insertion
00167   // fails, we have the answer already. If it succeeds, leave it there until we
00168   // compute the real answer to guard against recursive queries.
00169   if (A > B) std::swap(A, B);
00170   std::pair<CachedResultsTy::iterator, bool> Pair =
00171     CachedResults.insert(std::make_pair(ValuePairTy(A, B), true));
00172   if (!Pair.second)
00173     return Pair.first->second;
00174 
00175   bool Result = relatedCheck(A, B, DL);
00176   CachedResults[ValuePairTy(A, B)] = Result;
00177   return Result;
00178 }