1//===- ProvenanceAnalysis.cpp - ObjC ARC Optimization ---------------------===//
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/// \file
10///
11/// This file defines a special form of Alias Analysis called ``Provenance
12/// Analysis''. The word ``provenance'' refers to the history of the ownership
13/// of an object. Thus ``Provenance Analysis'' is an analysis which attempts to
14/// use various techniques to determine if locally
15///
16/// WARNING: This file knows about certain library functions. It recognizes them
17/// by name, and hardwires knowledge of their semantics.
18///
19/// WARNING: This file knows about how certain Objective-C library functions are
20/// used. Naive LLVM IR transformations which would otherwise be
21/// behavior-preserving may break these assumptions.
22///
23//===----------------------------------------------------------------------===//
24
25#include "ObjCARC.h"
26#include "ProvenanceAnalysis.h"
27#include "llvm/ADT/STLExtras.h"
28#include "llvm/ADT/SmallPtrSet.h"
29
30using namespace llvm;
31using namespace llvm::objcarc;
32
33bool ProvenanceAnalysis::relatedSelect(const SelectInst *A,
34                                       const Value *B) {
35  const DataLayout &DL = A->getModule()->getDataLayout();
36  // If the values are Selects with the same condition, we can do a more precise
37  // check: just check for relations between the values on corresponding arms.
38  if (const SelectInst *SB = dyn_cast<SelectInst>(B))
39    if (A->getCondition() == SB->getCondition())
40      return related(A->getTrueValue(), SB->getTrueValue(), DL) ||
41             related(A->getFalseValue(), SB->getFalseValue(), DL);
42
43  // Check both arms of the Select node individually.
44  return related(A->getTrueValue(), B, DL) ||
45         related(A->getFalseValue(), B, DL);
46}
47
48bool ProvenanceAnalysis::relatedPHI(const PHINode *A,
49                                    const Value *B) {
50  const DataLayout &DL = A->getModule()->getDataLayout();
51  // If the values are PHIs in the same block, we can do a more precise as well
52  // as efficient check: just check for relations between the values on
53  // corresponding edges.
54  if (const PHINode *PNB = dyn_cast<PHINode>(B))
55    if (PNB->getParent() == A->getParent()) {
56      for (unsigned i = 0, e = A->getNumIncomingValues(); i != e; ++i)
57        if (related(A->getIncomingValue(i),
58                    PNB->getIncomingValueForBlock(A->getIncomingBlock(i)), DL))
59          return true;
60      return false;
61    }
62
63  // Check each unique source of the PHI node against B.
64  SmallPtrSet<const Value *, 4> UniqueSrc;
65  for (Value *PV1 : A->incoming_values()) {
66    if (UniqueSrc.insert(PV1).second && related(PV1, B, DL))
67      return true;
68  }
69
70  // All of the arms checked out.
71  return false;
72}
73
74/// Test if the value of P, or any value covered by its provenance, is ever
75/// stored within the function (not counting callees).
76static bool IsStoredObjCPointer(const Value *P) {
77  SmallPtrSet<const Value *, 8> Visited;
78  SmallVector<const Value *, 8> Worklist;
79  Worklist.push_back(P);
80  Visited.insert(P);
81  do {
82    P = Worklist.pop_back_val();
83    for (const Use &U : P->uses()) {
84      const User *Ur = U.getUser();
85      if (isa<StoreInst>(Ur)) {
86        if (U.getOperandNo() == 0)
87          // The pointer is stored.
88          return true;
89        // The pointed is stored through.
90        continue;
91      }
92      if (isa<CallInst>(Ur))
93        // The pointer is passed as an argument, ignore this.
94        continue;
95      if (isa<PtrToIntInst>(P))
96        // Assume the worst.
97        return true;
98      if (Visited.insert(Ur).second)
99        Worklist.push_back(Ur);
100    }
101  } while (!Worklist.empty());
102
103  // Everything checked out.
104  return false;
105}
106
107bool ProvenanceAnalysis::relatedCheck(const Value *A, const Value *B,
108                                      const DataLayout &DL) {
109  // Skip past provenance pass-throughs.
110  A = GetUnderlyingObjCPtr(A, DL);
111  B = GetUnderlyingObjCPtr(B, DL);
112
113  // Quick check.
114  if (A == B)
115    return true;
116
117  // Ask regular AliasAnalysis, for a first approximation.
118  switch (AA->alias(A, B)) {
119  case NoAlias:
120    return false;
121  case MustAlias:
122  case PartialAlias:
123    return true;
124  case MayAlias:
125    break;
126  }
127
128  bool AIsIdentified = IsObjCIdentifiedObject(A);
129  bool BIsIdentified = IsObjCIdentifiedObject(B);
130
131  // An ObjC-Identified object can't alias a load if it is never locally stored.
132  if (AIsIdentified) {
133    // Check for an obvious escape.
134    if (isa<LoadInst>(B))
135      return IsStoredObjCPointer(A);
136    if (BIsIdentified) {
137      // Check for an obvious escape.
138      if (isa<LoadInst>(A))
139        return IsStoredObjCPointer(B);
140      // Both pointers are identified and escapes aren't an evident problem.
141      return false;
142    }
143  } else if (BIsIdentified) {
144    // Check for an obvious escape.
145    if (isa<LoadInst>(A))
146      return IsStoredObjCPointer(B);
147  }
148
149   // Special handling for PHI and Select.
150  if (const PHINode *PN = dyn_cast<PHINode>(A))
151    return relatedPHI(PN, B);
152  if (const PHINode *PN = dyn_cast<PHINode>(B))
153    return relatedPHI(PN, A);
154  if (const SelectInst *S = dyn_cast<SelectInst>(A))
155    return relatedSelect(S, B);
156  if (const SelectInst *S = dyn_cast<SelectInst>(B))
157    return relatedSelect(S, A);
158
159  // Conservative.
160  return true;
161}
162
163bool ProvenanceAnalysis::related(const Value *A, const Value *B,
164                                 const DataLayout &DL) {
165  // Begin by inserting a conservative value into the map. If the insertion
166  // fails, we have the answer already. If it succeeds, leave it there until we
167  // compute the real answer to guard against recursive queries.
168  if (A > B) std::swap(A, B);
169  std::pair<CachedResultsTy::iterator, bool> Pair =
170    CachedResults.insert(std::make_pair(ValuePairTy(A, B), true));
171  if (!Pair.second)
172    return Pair.first->second;
173
174  bool Result = relatedCheck(A, B, DL);
175  CachedResults[ValuePairTy(A, B)] = Result;
176  return Result;
177}
178