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
30 using namespace llvm;
31 using namespace llvm::objcarc;
32
relatedSelect(const SelectInst * A,const Value * B)33 bool 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
relatedPHI(const PHINode * A,const Value * B)48 bool 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 (unsigned i = 0, e = A->getNumIncomingValues(); i != e; ++i) {
66 const Value *PV1 = A->getIncomingValue(i);
67 if (UniqueSrc.insert(PV1).second && related(PV1, B, DL))
68 return true;
69 }
70
71 // All of the arms checked out.
72 return false;
73 }
74
75 /// Test if the value of P, or any value covered by its provenance, is ever
76 /// stored within the function (not counting callees).
IsStoredObjCPointer(const Value * P)77 static bool IsStoredObjCPointer(const Value *P) {
78 SmallPtrSet<const Value *, 8> Visited;
79 SmallVector<const Value *, 8> Worklist;
80 Worklist.push_back(P);
81 Visited.insert(P);
82 do {
83 P = Worklist.pop_back_val();
84 for (const Use &U : P->uses()) {
85 const User *Ur = U.getUser();
86 if (isa<StoreInst>(Ur)) {
87 if (U.getOperandNo() == 0)
88 // The pointer is stored.
89 return true;
90 // The pointed is stored through.
91 continue;
92 }
93 if (isa<CallInst>(Ur))
94 // The pointer is passed as an argument, ignore this.
95 continue;
96 if (isa<PtrToIntInst>(P))
97 // Assume the worst.
98 return true;
99 if (Visited.insert(Ur).second)
100 Worklist.push_back(Ur);
101 }
102 } while (!Worklist.empty());
103
104 // Everything checked out.
105 return false;
106 }
107
relatedCheck(const Value * A,const Value * B,const DataLayout & DL)108 bool ProvenanceAnalysis::relatedCheck(const Value *A, const Value *B,
109 const DataLayout &DL) {
110 // Skip past provenance pass-throughs.
111 A = GetUnderlyingObjCPtr(A, DL);
112 B = GetUnderlyingObjCPtr(B, DL);
113
114 // Quick check.
115 if (A == B)
116 return true;
117
118 // Ask regular AliasAnalysis, for a first approximation.
119 switch (AA->alias(A, B)) {
120 case AliasAnalysis::NoAlias:
121 return false;
122 case AliasAnalysis::MustAlias:
123 case AliasAnalysis::PartialAlias:
124 return true;
125 case AliasAnalysis::MayAlias:
126 break;
127 }
128
129 bool AIsIdentified = IsObjCIdentifiedObject(A);
130 bool BIsIdentified = IsObjCIdentifiedObject(B);
131
132 // An ObjC-Identified object can't alias a load if it is never locally stored.
133 if (AIsIdentified) {
134 // Check for an obvious escape.
135 if (isa<LoadInst>(B))
136 return IsStoredObjCPointer(A);
137 if (BIsIdentified) {
138 // Check for an obvious escape.
139 if (isa<LoadInst>(A))
140 return IsStoredObjCPointer(B);
141 // Both pointers are identified and escapes aren't an evident problem.
142 return false;
143 }
144 } else if (BIsIdentified) {
145 // Check for an obvious escape.
146 if (isa<LoadInst>(A))
147 return IsStoredObjCPointer(B);
148 }
149
150 // Special handling for PHI and Select.
151 if (const PHINode *PN = dyn_cast<PHINode>(A))
152 return relatedPHI(PN, B);
153 if (const PHINode *PN = dyn_cast<PHINode>(B))
154 return relatedPHI(PN, A);
155 if (const SelectInst *S = dyn_cast<SelectInst>(A))
156 return relatedSelect(S, B);
157 if (const SelectInst *S = dyn_cast<SelectInst>(B))
158 return relatedSelect(S, A);
159
160 // Conservative.
161 return true;
162 }
163
related(const Value * A,const Value * B,const DataLayout & DL)164 bool ProvenanceAnalysis::related(const Value *A, const Value *B,
165 const DataLayout &DL) {
166 // Begin by inserting a conservative value into the map. If the insertion
167 // fails, we have the answer already. If it succeeds, leave it there until we
168 // compute the real answer to guard against recursive queries.
169 if (A > B) std::swap(A, B);
170 std::pair<CachedResultsTy::iterator, bool> Pair =
171 CachedResults.insert(std::make_pair(ValuePairTy(A, B), true));
172 if (!Pair.second)
173 return Pair.first->second;
174
175 bool Result = relatedCheck(A, B, DL);
176 CachedResults[ValuePairTy(A, B)] = Result;
177 return Result;
178 }
179