1 //===- ProvenanceAnalysis.cpp - ObjC ARC Optimization ---------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
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 "ProvenanceAnalysis.h"
26 #include "llvm/ADT/SmallPtrSet.h"
27 #include "llvm/ADT/SmallVector.h"
28 #include "llvm/Analysis/AliasAnalysis.h"
29 #include "llvm/Analysis/ObjCARCAnalysisUtils.h"
30 #include "llvm/IR/Instructions.h"
31 #include "llvm/IR/Module.h"
32 #include "llvm/IR/Use.h"
33 #include "llvm/IR/User.h"
34 #include "llvm/IR/Value.h"
35 #include "llvm/Support/Casting.h"
36 #include <utility>
37
38 using namespace llvm;
39 using namespace llvm::objcarc;
40
relatedSelect(const SelectInst * A,const Value * B)41 bool ProvenanceAnalysis::relatedSelect(const SelectInst *A,
42 const Value *B) {
43 // If the values are Selects with the same condition, we can do a more precise
44 // check: just check for relations between the values on corresponding arms.
45 if (const SelectInst *SB = dyn_cast<SelectInst>(B)) {
46 if (A->getCondition() == SB->getCondition())
47 return related(A->getTrueValue(), SB->getTrueValue()) ||
48 related(A->getFalseValue(), SB->getFalseValue());
49
50 // Check both arms of B individually. Return false if neither arm is related
51 // to A.
52 if (!(related(SB->getTrueValue(), A) || related(SB->getFalseValue(), A)))
53 return false;
54 }
55
56 // Check both arms of the Select node individually.
57 return related(A->getTrueValue(), B) || related(A->getFalseValue(), B);
58 }
59
relatedPHI(const PHINode * A,const Value * B)60 bool ProvenanceAnalysis::relatedPHI(const PHINode *A,
61 const Value *B) {
62
63 auto comparePHISources = [this](const PHINode *PNA, const Value *B) -> bool {
64 // Check each unique source of the PHI node against B.
65 SmallPtrSet<const Value *, 4> UniqueSrc;
66 for (Value *PV1 : PNA->incoming_values()) {
67 if (UniqueSrc.insert(PV1).second && related(PV1, B))
68 return true;
69 }
70
71 // All of the arms checked out.
72 return false;
73 };
74
75 if (const PHINode *PNB = dyn_cast<PHINode>(B)) {
76 // If the values are PHIs in the same block, we can do a more precise as
77 // well as efficient check: just check for relations between the values on
78 // corresponding edges.
79 if (PNB->getParent() == A->getParent()) {
80 for (unsigned i = 0, e = A->getNumIncomingValues(); i != e; ++i)
81 if (related(A->getIncomingValue(i),
82 PNB->getIncomingValueForBlock(A->getIncomingBlock(i))))
83 return true;
84 return false;
85 }
86
87 if (!comparePHISources(PNB, A))
88 return false;
89 }
90
91 return comparePHISources(A, B);
92 }
93
94 /// Test if the value of P, or any value covered by its provenance, is ever
95 /// stored within the function (not counting callees).
IsStoredObjCPointer(const Value * P)96 static bool IsStoredObjCPointer(const Value *P) {
97 SmallPtrSet<const Value *, 8> Visited;
98 SmallVector<const Value *, 8> Worklist;
99 Worklist.push_back(P);
100 Visited.insert(P);
101 do {
102 P = Worklist.pop_back_val();
103 for (const Use &U : P->uses()) {
104 const User *Ur = U.getUser();
105 if (isa<StoreInst>(Ur)) {
106 if (U.getOperandNo() == 0)
107 // The pointer is stored.
108 return true;
109 // The pointed is stored through.
110 continue;
111 }
112 if (isa<CallInst>(Ur))
113 // The pointer is passed as an argument, ignore this.
114 continue;
115 if (isa<PtrToIntInst>(P))
116 // Assume the worst.
117 return true;
118 if (Visited.insert(Ur).second)
119 Worklist.push_back(Ur);
120 }
121 } while (!Worklist.empty());
122
123 // Everything checked out.
124 return false;
125 }
126
relatedCheck(const Value * A,const Value * B)127 bool ProvenanceAnalysis::relatedCheck(const Value *A, const Value *B) {
128 // Ask regular AliasAnalysis, for a first approximation.
129 switch (AA->alias(A, B)) {
130 case AliasResult::NoAlias:
131 return false;
132 case AliasResult::MustAlias:
133 case AliasResult::PartialAlias:
134 return true;
135 case AliasResult::MayAlias:
136 break;
137 }
138
139 bool AIsIdentified = IsObjCIdentifiedObject(A);
140 bool BIsIdentified = IsObjCIdentifiedObject(B);
141
142 // An ObjC-Identified object can't alias a load if it is never locally stored.
143
144 // Check for an obvious escape.
145 if ((AIsIdentified && isa<LoadInst>(B) && !IsStoredObjCPointer(A)) ||
146 (BIsIdentified && isa<LoadInst>(A) && !IsStoredObjCPointer(B)))
147 return false;
148
149 if ((AIsIdentified && isa<LoadInst>(B)) ||
150 (BIsIdentified && isa<LoadInst>(A)))
151 return true;
152
153 // Both pointers are identified and escapes aren't an evident problem.
154 if (AIsIdentified && BIsIdentified && !isa<LoadInst>(A) && !isa<LoadInst>(B))
155 return false;
156
157 // Special handling for PHI and Select.
158 if (const PHINode *PN = dyn_cast<PHINode>(A))
159 return relatedPHI(PN, B);
160 if (const PHINode *PN = dyn_cast<PHINode>(B))
161 return relatedPHI(PN, A);
162 if (const SelectInst *S = dyn_cast<SelectInst>(A))
163 return relatedSelect(S, B);
164 if (const SelectInst *S = dyn_cast<SelectInst>(B))
165 return relatedSelect(S, A);
166
167 // Conservative.
168 return true;
169 }
170
related(const Value * A,const Value * B)171 bool ProvenanceAnalysis::related(const Value *A, const Value *B) {
172 A = GetUnderlyingObjCPtrCached(A, UnderlyingObjCPtrCache);
173 B = GetUnderlyingObjCPtrCached(B, UnderlyingObjCPtrCache);
174
175 // Quick check.
176 if (A == B)
177 return true;
178
179 // Begin by inserting a conservative value into the map. If the insertion
180 // fails, we have the answer already. If it succeeds, leave it there until we
181 // compute the real answer to guard against recursive queries.
182 if (A > B) std::swap(A, B);
183 std::pair<CachedResultsTy::iterator, bool> Pair =
184 CachedResults.insert(std::make_pair(ValuePairTy(A, B), true));
185 if (!Pair.second)
186 return Pair.first->second;
187
188 bool Result = relatedCheck(A, B);
189 assert(relatedCheck(B, A) == Result &&
190 "relatedCheck result depending on order of parameters!");
191 CachedResults[ValuePairTy(A, B)] = Result;
192 return Result;
193 }
194