/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/ObjCARC/ProvenanceAnalysis.cpp
Line | Count | Source (jump to first uncovered line) |
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 | | |
41 | | bool ProvenanceAnalysis::relatedSelect(const SelectInst *A, |
42 | 5 | const Value *B) { |
43 | 5 | const DataLayout &DL = A->getModule()->getDataLayout(); |
44 | 5 | // If the values are Selects with the same condition, we can do a more precise |
45 | 5 | // check: just check for relations between the values on corresponding arms. |
46 | 5 | if (const SelectInst *SB = dyn_cast<SelectInst>(B)) |
47 | 0 | if (A->getCondition() == SB->getCondition()) |
48 | 0 | return related(A->getTrueValue(), SB->getTrueValue(), DL) || |
49 | 0 | related(A->getFalseValue(), SB->getFalseValue(), DL); |
50 | 5 | |
51 | 5 | // Check both arms of the Select node individually. |
52 | 5 | return related(A->getTrueValue(), B, DL) || |
53 | 5 | related(A->getFalseValue(), B, DL)0 ; |
54 | 5 | } |
55 | | |
56 | | bool ProvenanceAnalysis::relatedPHI(const PHINode *A, |
57 | 140 | const Value *B) { |
58 | 140 | const DataLayout &DL = A->getModule()->getDataLayout(); |
59 | 140 | // If the values are PHIs in the same block, we can do a more precise as well |
60 | 140 | // as efficient check: just check for relations between the values on |
61 | 140 | // corresponding edges. |
62 | 140 | if (const PHINode *PNB = dyn_cast<PHINode>(B)) |
63 | 10 | if (PNB->getParent() == A->getParent()) { |
64 | 13 | for (unsigned i = 0, e = A->getNumIncomingValues(); i != e; ++i9 ) |
65 | 11 | if (related(A->getIncomingValue(i), |
66 | 11 | PNB->getIncomingValueForBlock(A->getIncomingBlock(i)), DL)) |
67 | 2 | return true; |
68 | 4 | return false2 ; |
69 | 136 | } |
70 | 136 | |
71 | 136 | // Check each unique source of the PHI node against B. |
72 | 136 | SmallPtrSet<const Value *, 4> UniqueSrc; |
73 | 434 | for (Value *PV1 : A->incoming_values()) { |
74 | 434 | if (UniqueSrc.insert(PV1).second && related(PV1, B, DL)295 ) |
75 | 27 | return true; |
76 | 434 | } |
77 | 136 | |
78 | 136 | // All of the arms checked out. |
79 | 136 | return false109 ; |
80 | 136 | } |
81 | | |
82 | | /// Test if the value of P, or any value covered by its provenance, is ever |
83 | | /// stored within the function (not counting callees). |
84 | 376 | static bool IsStoredObjCPointer(const Value *P) { |
85 | 376 | SmallPtrSet<const Value *, 8> Visited; |
86 | 376 | SmallVector<const Value *, 8> Worklist; |
87 | 376 | Worklist.push_back(P); |
88 | 376 | Visited.insert(P); |
89 | 1.32k | do { |
90 | 1.32k | P = Worklist.pop_back_val(); |
91 | 2.15k | for (const Use &U : P->uses()) { |
92 | 2.15k | const User *Ur = U.getUser(); |
93 | 2.15k | if (isa<StoreInst>(Ur)) { |
94 | 239 | if (U.getOperandNo() == 0) |
95 | 44 | // The pointer is stored. |
96 | 44 | return true; |
97 | 195 | // The pointed is stored through. |
98 | 195 | continue; |
99 | 195 | } |
100 | 1.91k | if (isa<CallInst>(Ur)) |
101 | 820 | // The pointer is passed as an argument, ignore this. |
102 | 820 | continue; |
103 | 1.09k | if (isa<PtrToIntInst>(P)) |
104 | 0 | // Assume the worst. |
105 | 0 | return true; |
106 | 1.09k | if (Visited.insert(Ur).second) |
107 | 948 | Worklist.push_back(Ur); |
108 | 1.09k | } |
109 | 1.32k | } while (!Worklist.empty()1.28k ); |
110 | 376 | |
111 | 376 | // Everything checked out. |
112 | 376 | return false332 ; |
113 | 376 | } |
114 | | |
115 | | bool ProvenanceAnalysis::relatedCheck(const Value *A, const Value *B, |
116 | 780 | const DataLayout &DL) { |
117 | 780 | // Ask regular AliasAnalysis, for a first approximation. |
118 | 780 | switch (AA->alias(A, B)) { |
119 | 780 | case NoAlias: |
120 | 73 | return false; |
121 | 780 | case MustAlias: |
122 | 0 | case PartialAlias: |
123 | 0 | return true; |
124 | 707 | case MayAlias: |
125 | 707 | break; |
126 | 707 | } |
127 | 707 | |
128 | 707 | bool AIsIdentified = IsObjCIdentifiedObject(A); |
129 | 707 | bool BIsIdentified = IsObjCIdentifiedObject(B); |
130 | 707 | |
131 | 707 | // An ObjC-Identified object can't alias a load if it is never locally stored. |
132 | 707 | if (AIsIdentified) { |
133 | 589 | // Check for an obvious escape. |
134 | 589 | if (isa<LoadInst>(B)) |
135 | 345 | return IsStoredObjCPointer(A); |
136 | 244 | if (BIsIdentified) { |
137 | 173 | // Check for an obvious escape. |
138 | 173 | if (isa<LoadInst>(A)) |
139 | 6 | return IsStoredObjCPointer(B); |
140 | 167 | // Both pointers are identified and escapes aren't an evident problem. |
141 | 167 | return false; |
142 | 167 | } |
143 | 118 | } else if (BIsIdentified) { |
144 | 51 | // Check for an obvious escape. |
145 | 51 | if (isa<LoadInst>(A)) |
146 | 25 | return IsStoredObjCPointer(B); |
147 | 164 | } |
148 | 164 | |
149 | 164 | // Special handling for PHI and Select. |
150 | 164 | if (const PHINode *PN = dyn_cast<PHINode>(A)) |
151 | 56 | return relatedPHI(PN, B); |
152 | 108 | if (const PHINode *PN = dyn_cast<PHINode>(B)) |
153 | 84 | return relatedPHI(PN, A); |
154 | 24 | if (const SelectInst *S = dyn_cast<SelectInst>(A)) |
155 | 0 | return relatedSelect(S, B); |
156 | 24 | if (const SelectInst *S = dyn_cast<SelectInst>(B)) |
157 | 5 | return relatedSelect(S, A); |
158 | 19 | |
159 | 19 | // Conservative. |
160 | 19 | return true; |
161 | 19 | } |
162 | | |
163 | | bool ProvenanceAnalysis::related(const Value *A, const Value *B, |
164 | 1.60k | const DataLayout &DL) { |
165 | 1.60k | A = GetUnderlyingObjCPtrCached(A, DL, UnderlyingObjCPtrCache); |
166 | 1.60k | B = GetUnderlyingObjCPtrCached(B, DL, UnderlyingObjCPtrCache); |
167 | 1.60k | |
168 | 1.60k | // Quick check. |
169 | 1.60k | if (A == B) |
170 | 337 | return true; |
171 | 1.27k | |
172 | 1.27k | // Begin by inserting a conservative value into the map. If the insertion |
173 | 1.27k | // fails, we have the answer already. If it succeeds, leave it there until we |
174 | 1.27k | // compute the real answer to guard against recursive queries. |
175 | 1.27k | if (A > B) std::swap(A, B)397 ; |
176 | 1.27k | std::pair<CachedResultsTy::iterator, bool> Pair = |
177 | 1.27k | CachedResults.insert(std::make_pair(ValuePairTy(A, B), true)); |
178 | 1.27k | if (!Pair.second) |
179 | 492 | return Pair.first->second; |
180 | 780 | |
181 | 780 | bool Result = relatedCheck(A, B, DL); |
182 | 780 | CachedResults[ValuePairTy(A, B)] = Result; |
183 | 780 | return Result; |
184 | 780 | } |