]>
Commit | Line | Data |
---|---|---|
970d7e83 LB |
1 | //===- ObjCARCOpts.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 | /// This file defines ObjC ARC optimizations. ARC stands for Automatic | |
11 | /// Reference Counting and is a system for managing reference counts for objects | |
12 | /// in Objective C. | |
13 | /// | |
14 | /// The optimizations performed include elimination of redundant, partially | |
15 | /// redundant, and inconsequential reference count operations, elimination of | |
16 | /// redundant weak pointer operations, and numerous minor simplifications. | |
17 | /// | |
18 | /// WARNING: This file knows about certain library functions. It recognizes them | |
19 | /// by name, and hardwires knowledge of their semantics. | |
20 | /// | |
21 | /// WARNING: This file knows about how certain Objective-C library functions are | |
22 | /// used. Naive LLVM IR transformations which would otherwise be | |
23 | /// behavior-preserving may break these assumptions. | |
24 | /// | |
25 | //===----------------------------------------------------------------------===// | |
26 | ||
970d7e83 | 27 | #include "ObjCARC.h" |
1a4d82fc | 28 | #include "ARCRuntimeEntryPoints.h" |
970d7e83 LB |
29 | #include "DependencyAnalysis.h" |
30 | #include "ObjCARCAliasAnalysis.h" | |
31 | #include "ProvenanceAnalysis.h" | |
32 | #include "llvm/ADT/DenseMap.h" | |
1a4d82fc | 33 | #include "llvm/ADT/DenseSet.h" |
970d7e83 LB |
34 | #include "llvm/ADT/STLExtras.h" |
35 | #include "llvm/ADT/SmallPtrSet.h" | |
36 | #include "llvm/ADT/Statistic.h" | |
1a4d82fc JJ |
37 | #include "llvm/IR/CFG.h" |
38 | #include "llvm/IR/IRBuilder.h" | |
970d7e83 | 39 | #include "llvm/IR/LLVMContext.h" |
970d7e83 LB |
40 | #include "llvm/Support/Debug.h" |
41 | #include "llvm/Support/raw_ostream.h" | |
42 | ||
43 | using namespace llvm; | |
44 | using namespace llvm::objcarc; | |
45 | ||
1a4d82fc JJ |
46 | #define DEBUG_TYPE "objc-arc-opts" |
47 | ||
970d7e83 LB |
48 | /// \defgroup MiscUtils Miscellaneous utilities that are not ARC specific. |
49 | /// @{ | |
50 | ||
51 | namespace { | |
52 | /// \brief An associative container with fast insertion-order (deterministic) | |
53 | /// iteration over its elements. Plus the special blot operation. | |
54 | template<class KeyT, class ValueT> | |
55 | class MapVector { | |
56 | /// Map keys to indices in Vector. | |
57 | typedef DenseMap<KeyT, size_t> MapTy; | |
58 | MapTy Map; | |
59 | ||
60 | typedef std::vector<std::pair<KeyT, ValueT> > VectorTy; | |
61 | /// Keys and values. | |
62 | VectorTy Vector; | |
63 | ||
64 | public: | |
65 | typedef typename VectorTy::iterator iterator; | |
66 | typedef typename VectorTy::const_iterator const_iterator; | |
67 | iterator begin() { return Vector.begin(); } | |
68 | iterator end() { return Vector.end(); } | |
69 | const_iterator begin() const { return Vector.begin(); } | |
70 | const_iterator end() const { return Vector.end(); } | |
71 | ||
72 | #ifdef XDEBUG | |
73 | ~MapVector() { | |
74 | assert(Vector.size() >= Map.size()); // May differ due to blotting. | |
75 | for (typename MapTy::const_iterator I = Map.begin(), E = Map.end(); | |
76 | I != E; ++I) { | |
77 | assert(I->second < Vector.size()); | |
78 | assert(Vector[I->second].first == I->first); | |
79 | } | |
80 | for (typename VectorTy::const_iterator I = Vector.begin(), | |
81 | E = Vector.end(); I != E; ++I) | |
82 | assert(!I->first || | |
83 | (Map.count(I->first) && | |
84 | Map[I->first] == size_t(I - Vector.begin()))); | |
85 | } | |
86 | #endif | |
87 | ||
88 | ValueT &operator[](const KeyT &Arg) { | |
89 | std::pair<typename MapTy::iterator, bool> Pair = | |
90 | Map.insert(std::make_pair(Arg, size_t(0))); | |
91 | if (Pair.second) { | |
92 | size_t Num = Vector.size(); | |
93 | Pair.first->second = Num; | |
94 | Vector.push_back(std::make_pair(Arg, ValueT())); | |
95 | return Vector[Num].second; | |
96 | } | |
97 | return Vector[Pair.first->second].second; | |
98 | } | |
99 | ||
100 | std::pair<iterator, bool> | |
101 | insert(const std::pair<KeyT, ValueT> &InsertPair) { | |
102 | std::pair<typename MapTy::iterator, bool> Pair = | |
103 | Map.insert(std::make_pair(InsertPair.first, size_t(0))); | |
104 | if (Pair.second) { | |
105 | size_t Num = Vector.size(); | |
106 | Pair.first->second = Num; | |
107 | Vector.push_back(InsertPair); | |
108 | return std::make_pair(Vector.begin() + Num, true); | |
109 | } | |
110 | return std::make_pair(Vector.begin() + Pair.first->second, false); | |
111 | } | |
112 | ||
1a4d82fc JJ |
113 | iterator find(const KeyT &Key) { |
114 | typename MapTy::iterator It = Map.find(Key); | |
115 | if (It == Map.end()) return Vector.end(); | |
116 | return Vector.begin() + It->second; | |
117 | } | |
118 | ||
970d7e83 LB |
119 | const_iterator find(const KeyT &Key) const { |
120 | typename MapTy::const_iterator It = Map.find(Key); | |
121 | if (It == Map.end()) return Vector.end(); | |
122 | return Vector.begin() + It->second; | |
123 | } | |
124 | ||
125 | /// This is similar to erase, but instead of removing the element from the | |
126 | /// vector, it just zeros out the key in the vector. This leaves iterators | |
127 | /// intact, but clients must be prepared for zeroed-out keys when iterating. | |
128 | void blot(const KeyT &Key) { | |
129 | typename MapTy::iterator It = Map.find(Key); | |
130 | if (It == Map.end()) return; | |
131 | Vector[It->second].first = KeyT(); | |
132 | Map.erase(It); | |
133 | } | |
134 | ||
135 | void clear() { | |
136 | Map.clear(); | |
137 | Vector.clear(); | |
138 | } | |
139 | }; | |
140 | } | |
141 | ||
142 | /// @} | |
143 | /// | |
144 | /// \defgroup ARCUtilities Utility declarations/definitions specific to ARC. | |
145 | /// @{ | |
146 | ||
147 | /// \brief This is similar to StripPointerCastsAndObjCCalls but it stops as soon | |
148 | /// as it finds a value with multiple uses. | |
149 | static const Value *FindSingleUseIdentifiedObject(const Value *Arg) { | |
150 | if (Arg->hasOneUse()) { | |
151 | if (const BitCastInst *BC = dyn_cast<BitCastInst>(Arg)) | |
152 | return FindSingleUseIdentifiedObject(BC->getOperand(0)); | |
153 | if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Arg)) | |
154 | if (GEP->hasAllZeroIndices()) | |
155 | return FindSingleUseIdentifiedObject(GEP->getPointerOperand()); | |
156 | if (IsForwarding(GetBasicInstructionClass(Arg))) | |
157 | return FindSingleUseIdentifiedObject( | |
158 | cast<CallInst>(Arg)->getArgOperand(0)); | |
159 | if (!IsObjCIdentifiedObject(Arg)) | |
1a4d82fc | 160 | return nullptr; |
970d7e83 LB |
161 | return Arg; |
162 | } | |
163 | ||
164 | // If we found an identifiable object but it has multiple uses, but they are | |
165 | // trivial uses, we can still consider this to be a single-use value. | |
166 | if (IsObjCIdentifiedObject(Arg)) { | |
1a4d82fc | 167 | for (const User *U : Arg->users()) |
970d7e83 | 168 | if (!U->use_empty() || StripPointerCastsAndObjCCalls(U) != Arg) |
1a4d82fc | 169 | return nullptr; |
970d7e83 LB |
170 | |
171 | return Arg; | |
172 | } | |
173 | ||
1a4d82fc | 174 | return nullptr; |
970d7e83 LB |
175 | } |
176 | ||
1a4d82fc JJ |
177 | /// This is a wrapper around getUnderlyingObjCPtr along the lines of |
178 | /// GetUnderlyingObjects except that it returns early when it sees the first | |
179 | /// alloca. | |
180 | static inline bool AreAnyUnderlyingObjectsAnAlloca(const Value *V) { | |
181 | SmallPtrSet<const Value *, 4> Visited; | |
970d7e83 | 182 | SmallVector<const Value *, 4> Worklist; |
1a4d82fc | 183 | Worklist.push_back(V); |
970d7e83 | 184 | do { |
1a4d82fc JJ |
185 | const Value *P = Worklist.pop_back_val(); |
186 | P = GetUnderlyingObjCPtr(P); | |
970d7e83 | 187 | |
1a4d82fc JJ |
188 | if (isa<AllocaInst>(P)) |
189 | return true; | |
970d7e83 | 190 | |
85aaf69f | 191 | if (!Visited.insert(P).second) |
1a4d82fc | 192 | continue; |
970d7e83 | 193 | |
1a4d82fc JJ |
194 | if (const SelectInst *SI = dyn_cast<const SelectInst>(P)) { |
195 | Worklist.push_back(SI->getTrueValue()); | |
196 | Worklist.push_back(SI->getFalseValue()); | |
197 | continue; | |
198 | } | |
970d7e83 | 199 | |
1a4d82fc JJ |
200 | if (const PHINode *PN = dyn_cast<const PHINode>(P)) { |
201 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) | |
202 | Worklist.push_back(PN->getIncomingValue(i)); | |
203 | continue; | |
970d7e83 LB |
204 | } |
205 | } while (!Worklist.empty()); | |
206 | ||
970d7e83 LB |
207 | return false; |
208 | } | |
209 | ||
1a4d82fc | 210 | |
970d7e83 LB |
211 | /// @} |
212 | /// | |
213 | /// \defgroup ARCOpt ARC Optimization. | |
214 | /// @{ | |
215 | ||
216 | // TODO: On code like this: | |
217 | // | |
218 | // objc_retain(%x) | |
219 | // stuff_that_cannot_release() | |
220 | // objc_autorelease(%x) | |
221 | // stuff_that_cannot_release() | |
222 | // objc_retain(%x) | |
223 | // stuff_that_cannot_release() | |
224 | // objc_autorelease(%x) | |
225 | // | |
226 | // The second retain and autorelease can be deleted. | |
227 | ||
228 | // TODO: It should be possible to delete | |
229 | // objc_autoreleasePoolPush and objc_autoreleasePoolPop | |
230 | // pairs if nothing is actually autoreleased between them. Also, autorelease | |
231 | // calls followed by objc_autoreleasePoolPop calls (perhaps in ObjC++ code | |
232 | // after inlining) can be turned into plain release calls. | |
233 | ||
234 | // TODO: Critical-edge splitting. If the optimial insertion point is | |
235 | // a critical edge, the current algorithm has to fail, because it doesn't | |
236 | // know how to split edges. It should be possible to make the optimizer | |
237 | // think in terms of edges, rather than blocks, and then split critical | |
238 | // edges on demand. | |
239 | ||
240 | // TODO: OptimizeSequences could generalized to be Interprocedural. | |
241 | ||
242 | // TODO: Recognize that a bunch of other objc runtime calls have | |
243 | // non-escaping arguments and non-releasing arguments, and may be | |
244 | // non-autoreleasing. | |
245 | ||
246 | // TODO: Sink autorelease calls as far as possible. Unfortunately we | |
247 | // usually can't sink them past other calls, which would be the main | |
248 | // case where it would be useful. | |
249 | ||
250 | // TODO: The pointer returned from objc_loadWeakRetained is retained. | |
251 | ||
252 | // TODO: Delete release+retain pairs (rare). | |
253 | ||
254 | STATISTIC(NumNoops, "Number of no-op objc calls eliminated"); | |
255 | STATISTIC(NumPartialNoops, "Number of partially no-op objc calls eliminated"); | |
256 | STATISTIC(NumAutoreleases,"Number of autoreleases converted to releases"); | |
257 | STATISTIC(NumRets, "Number of return value forwarding " | |
1a4d82fc | 258 | "retain+autoreleases eliminated"); |
970d7e83 LB |
259 | STATISTIC(NumRRs, "Number of retain+release paths eliminated"); |
260 | STATISTIC(NumPeeps, "Number of calls peephole-optimized"); | |
1a4d82fc JJ |
261 | #ifndef NDEBUG |
262 | STATISTIC(NumRetainsBeforeOpt, | |
263 | "Number of retains before optimization"); | |
264 | STATISTIC(NumReleasesBeforeOpt, | |
265 | "Number of releases before optimization"); | |
266 | STATISTIC(NumRetainsAfterOpt, | |
267 | "Number of retains after optimization"); | |
268 | STATISTIC(NumReleasesAfterOpt, | |
269 | "Number of releases after optimization"); | |
270 | #endif | |
970d7e83 LB |
271 | |
272 | namespace { | |
273 | /// \enum Sequence | |
274 | /// | |
275 | /// \brief A sequence of states that a pointer may go through in which an | |
276 | /// objc_retain and objc_release are actually needed. | |
277 | enum Sequence { | |
278 | S_None, | |
279 | S_Retain, ///< objc_retain(x). | |
280 | S_CanRelease, ///< foo(x) -- x could possibly see a ref count decrement. | |
281 | S_Use, ///< any use of x. | |
282 | S_Stop, ///< like S_Release, but code motion is stopped. | |
283 | S_Release, ///< objc_release(x). | |
284 | S_MovableRelease ///< objc_release(x), !clang.imprecise_release. | |
285 | }; | |
286 | ||
287 | raw_ostream &operator<<(raw_ostream &OS, const Sequence S) | |
288 | LLVM_ATTRIBUTE_UNUSED; | |
289 | raw_ostream &operator<<(raw_ostream &OS, const Sequence S) { | |
290 | switch (S) { | |
291 | case S_None: | |
292 | return OS << "S_None"; | |
293 | case S_Retain: | |
294 | return OS << "S_Retain"; | |
295 | case S_CanRelease: | |
296 | return OS << "S_CanRelease"; | |
297 | case S_Use: | |
298 | return OS << "S_Use"; | |
299 | case S_Release: | |
300 | return OS << "S_Release"; | |
301 | case S_MovableRelease: | |
302 | return OS << "S_MovableRelease"; | |
303 | case S_Stop: | |
304 | return OS << "S_Stop"; | |
305 | } | |
306 | llvm_unreachable("Unknown sequence type."); | |
307 | } | |
308 | } | |
309 | ||
310 | static Sequence MergeSeqs(Sequence A, Sequence B, bool TopDown) { | |
311 | // The easy cases. | |
312 | if (A == B) | |
313 | return A; | |
314 | if (A == S_None || B == S_None) | |
315 | return S_None; | |
316 | ||
317 | if (A > B) std::swap(A, B); | |
318 | if (TopDown) { | |
319 | // Choose the side which is further along in the sequence. | |
320 | if ((A == S_Retain || A == S_CanRelease) && | |
321 | (B == S_CanRelease || B == S_Use)) | |
322 | return B; | |
323 | } else { | |
324 | // Choose the side which is further along in the sequence. | |
325 | if ((A == S_Use || A == S_CanRelease) && | |
326 | (B == S_Use || B == S_Release || B == S_Stop || B == S_MovableRelease)) | |
327 | return A; | |
328 | // If both sides are releases, choose the more conservative one. | |
329 | if (A == S_Stop && (B == S_Release || B == S_MovableRelease)) | |
330 | return A; | |
331 | if (A == S_Release && B == S_MovableRelease) | |
332 | return A; | |
333 | } | |
334 | ||
335 | return S_None; | |
336 | } | |
337 | ||
338 | namespace { | |
339 | /// \brief Unidirectional information about either a | |
340 | /// retain-decrement-use-release sequence or release-use-decrement-retain | |
1a4d82fc | 341 | /// reverse sequence. |
970d7e83 LB |
342 | struct RRInfo { |
343 | /// After an objc_retain, the reference count of the referenced | |
344 | /// object is known to be positive. Similarly, before an objc_release, the | |
345 | /// reference count of the referenced object is known to be positive. If | |
346 | /// there are retain-release pairs in code regions where the retain count | |
347 | /// is known to be positive, they can be eliminated, regardless of any side | |
348 | /// effects between them. | |
349 | /// | |
350 | /// Also, a retain+release pair nested within another retain+release | |
351 | /// pair all on the known same pointer value can be eliminated, regardless | |
352 | /// of any intervening side effects. | |
353 | /// | |
354 | /// KnownSafe is true when either of these conditions is satisfied. | |
355 | bool KnownSafe; | |
356 | ||
970d7e83 LB |
357 | /// True of the objc_release calls are all marked with the "tail" keyword. |
358 | bool IsTailCallRelease; | |
359 | ||
360 | /// If the Calls are objc_release calls and they all have a | |
361 | /// clang.imprecise_release tag, this is the metadata tag. | |
362 | MDNode *ReleaseMetadata; | |
363 | ||
364 | /// For a top-down sequence, the set of objc_retains or | |
365 | /// objc_retainBlocks. For bottom-up, the set of objc_releases. | |
366 | SmallPtrSet<Instruction *, 2> Calls; | |
367 | ||
368 | /// The set of optimal insert positions for moving calls in the opposite | |
369 | /// sequence. | |
370 | SmallPtrSet<Instruction *, 2> ReverseInsertPts; | |
371 | ||
1a4d82fc JJ |
372 | /// If this is true, we cannot perform code motion but can still remove |
373 | /// retain/release pairs. | |
374 | bool CFGHazardAfflicted; | |
375 | ||
970d7e83 | 376 | RRInfo() : |
1a4d82fc JJ |
377 | KnownSafe(false), IsTailCallRelease(false), ReleaseMetadata(nullptr), |
378 | CFGHazardAfflicted(false) {} | |
970d7e83 LB |
379 | |
380 | void clear(); | |
1a4d82fc JJ |
381 | |
382 | /// Conservatively merge the two RRInfo. Returns true if a partial merge has | |
383 | /// occurred, false otherwise. | |
384 | bool Merge(const RRInfo &Other); | |
385 | ||
970d7e83 LB |
386 | }; |
387 | } | |
388 | ||
389 | void RRInfo::clear() { | |
390 | KnownSafe = false; | |
970d7e83 | 391 | IsTailCallRelease = false; |
1a4d82fc | 392 | ReleaseMetadata = nullptr; |
970d7e83 LB |
393 | Calls.clear(); |
394 | ReverseInsertPts.clear(); | |
1a4d82fc JJ |
395 | CFGHazardAfflicted = false; |
396 | } | |
397 | ||
398 | bool RRInfo::Merge(const RRInfo &Other) { | |
399 | // Conservatively merge the ReleaseMetadata information. | |
400 | if (ReleaseMetadata != Other.ReleaseMetadata) | |
401 | ReleaseMetadata = nullptr; | |
402 | ||
403 | // Conservatively merge the boolean state. | |
404 | KnownSafe &= Other.KnownSafe; | |
405 | IsTailCallRelease &= Other.IsTailCallRelease; | |
406 | CFGHazardAfflicted |= Other.CFGHazardAfflicted; | |
407 | ||
408 | // Merge the call sets. | |
409 | Calls.insert(Other.Calls.begin(), Other.Calls.end()); | |
410 | ||
411 | // Merge the insert point sets. If there are any differences, | |
412 | // that makes this a partial merge. | |
413 | bool Partial = ReverseInsertPts.size() != Other.ReverseInsertPts.size(); | |
414 | for (Instruction *Inst : Other.ReverseInsertPts) | |
85aaf69f | 415 | Partial |= ReverseInsertPts.insert(Inst).second; |
1a4d82fc | 416 | return Partial; |
970d7e83 LB |
417 | } |
418 | ||
419 | namespace { | |
420 | /// \brief This class summarizes several per-pointer runtime properties which | |
421 | /// are propogated through the flow graph. | |
422 | class PtrState { | |
423 | /// True if the reference count is known to be incremented. | |
424 | bool KnownPositiveRefCount; | |
425 | ||
1a4d82fc | 426 | /// True if we've seen an opportunity for partial RR elimination, such as |
970d7e83 LB |
427 | /// pushing calls into a CFG triangle or into one side of a CFG diamond. |
428 | bool Partial; | |
429 | ||
430 | /// The current position in the sequence. | |
1a4d82fc | 431 | unsigned char Seq : 8; |
970d7e83 | 432 | |
970d7e83 | 433 | /// Unidirectional information about the current sequence. |
970d7e83 LB |
434 | RRInfo RRI; |
435 | ||
1a4d82fc | 436 | public: |
970d7e83 LB |
437 | PtrState() : KnownPositiveRefCount(false), Partial(false), |
438 | Seq(S_None) {} | |
439 | ||
1a4d82fc JJ |
440 | |
441 | bool IsKnownSafe() const { | |
442 | return RRI.KnownSafe; | |
443 | } | |
444 | ||
445 | void SetKnownSafe(const bool NewValue) { | |
446 | RRI.KnownSafe = NewValue; | |
447 | } | |
448 | ||
449 | bool IsTailCallRelease() const { | |
450 | return RRI.IsTailCallRelease; | |
451 | } | |
452 | ||
453 | void SetTailCallRelease(const bool NewValue) { | |
454 | RRI.IsTailCallRelease = NewValue; | |
455 | } | |
456 | ||
457 | bool IsTrackingImpreciseReleases() const { | |
458 | return RRI.ReleaseMetadata != nullptr; | |
459 | } | |
460 | ||
461 | const MDNode *GetReleaseMetadata() const { | |
462 | return RRI.ReleaseMetadata; | |
463 | } | |
464 | ||
465 | void SetReleaseMetadata(MDNode *NewValue) { | |
466 | RRI.ReleaseMetadata = NewValue; | |
467 | } | |
468 | ||
469 | bool IsCFGHazardAfflicted() const { | |
470 | return RRI.CFGHazardAfflicted; | |
471 | } | |
472 | ||
473 | void SetCFGHazardAfflicted(const bool NewValue) { | |
474 | RRI.CFGHazardAfflicted = NewValue; | |
475 | } | |
476 | ||
970d7e83 | 477 | void SetKnownPositiveRefCount() { |
1a4d82fc | 478 | DEBUG(dbgs() << "Setting Known Positive.\n"); |
970d7e83 LB |
479 | KnownPositiveRefCount = true; |
480 | } | |
481 | ||
1a4d82fc JJ |
482 | void ClearKnownPositiveRefCount() { |
483 | DEBUG(dbgs() << "Clearing Known Positive.\n"); | |
970d7e83 LB |
484 | KnownPositiveRefCount = false; |
485 | } | |
486 | ||
1a4d82fc | 487 | bool HasKnownPositiveRefCount() const { |
970d7e83 LB |
488 | return KnownPositiveRefCount; |
489 | } | |
490 | ||
491 | void SetSeq(Sequence NewSeq) { | |
1a4d82fc | 492 | DEBUG(dbgs() << "Old: " << Seq << "; New: " << NewSeq << "\n"); |
970d7e83 LB |
493 | Seq = NewSeq; |
494 | } | |
495 | ||
496 | Sequence GetSeq() const { | |
1a4d82fc | 497 | return static_cast<Sequence>(Seq); |
970d7e83 LB |
498 | } |
499 | ||
500 | void ClearSequenceProgress() { | |
501 | ResetSequenceProgress(S_None); | |
502 | } | |
503 | ||
504 | void ResetSequenceProgress(Sequence NewSeq) { | |
1a4d82fc JJ |
505 | DEBUG(dbgs() << "Resetting sequence progress.\n"); |
506 | SetSeq(NewSeq); | |
970d7e83 LB |
507 | Partial = false; |
508 | RRI.clear(); | |
509 | } | |
510 | ||
511 | void Merge(const PtrState &Other, bool TopDown); | |
1a4d82fc JJ |
512 | |
513 | void InsertCall(Instruction *I) { | |
514 | RRI.Calls.insert(I); | |
515 | } | |
516 | ||
517 | void InsertReverseInsertPt(Instruction *I) { | |
518 | RRI.ReverseInsertPts.insert(I); | |
519 | } | |
520 | ||
521 | void ClearReverseInsertPts() { | |
522 | RRI.ReverseInsertPts.clear(); | |
523 | } | |
524 | ||
525 | bool HasReverseInsertPts() const { | |
526 | return !RRI.ReverseInsertPts.empty(); | |
527 | } | |
528 | ||
529 | const RRInfo &GetRRInfo() const { | |
530 | return RRI; | |
531 | } | |
970d7e83 LB |
532 | }; |
533 | } | |
534 | ||
535 | void | |
536 | PtrState::Merge(const PtrState &Other, bool TopDown) { | |
1a4d82fc JJ |
537 | Seq = MergeSeqs(GetSeq(), Other.GetSeq(), TopDown); |
538 | KnownPositiveRefCount &= Other.KnownPositiveRefCount; | |
970d7e83 LB |
539 | |
540 | // If we're not in a sequence (anymore), drop all associated state. | |
541 | if (Seq == S_None) { | |
542 | Partial = false; | |
543 | RRI.clear(); | |
544 | } else if (Partial || Other.Partial) { | |
545 | // If we're doing a merge on a path that's previously seen a partial | |
546 | // merge, conservatively drop the sequence, to avoid doing partial | |
547 | // RR elimination. If the branch predicates for the two merge differ, | |
548 | // mixing them is unsafe. | |
549 | ClearSequenceProgress(); | |
550 | } else { | |
1a4d82fc JJ |
551 | // Otherwise merge the other PtrState's RRInfo into our RRInfo. At this |
552 | // point, we know that currently we are not partial. Stash whether or not | |
553 | // the merge operation caused us to undergo a partial merging of reverse | |
554 | // insertion points. | |
555 | Partial = RRI.Merge(Other.RRI); | |
970d7e83 LB |
556 | } |
557 | } | |
558 | ||
559 | namespace { | |
560 | /// \brief Per-BasicBlock state. | |
561 | class BBState { | |
562 | /// The number of unique control paths from the entry which can reach this | |
563 | /// block. | |
564 | unsigned TopDownPathCount; | |
565 | ||
566 | /// The number of unique control paths to exits from this block. | |
567 | unsigned BottomUpPathCount; | |
568 | ||
569 | /// A type for PerPtrTopDown and PerPtrBottomUp. | |
570 | typedef MapVector<const Value *, PtrState> MapTy; | |
571 | ||
572 | /// The top-down traversal uses this to record information known about a | |
573 | /// pointer at the bottom of each block. | |
574 | MapTy PerPtrTopDown; | |
575 | ||
576 | /// The bottom-up traversal uses this to record information known about a | |
577 | /// pointer at the top of each block. | |
578 | MapTy PerPtrBottomUp; | |
579 | ||
580 | /// Effective predecessors of the current block ignoring ignorable edges and | |
581 | /// ignored backedges. | |
582 | SmallVector<BasicBlock *, 2> Preds; | |
583 | /// Effective successors of the current block ignoring ignorable edges and | |
584 | /// ignored backedges. | |
585 | SmallVector<BasicBlock *, 2> Succs; | |
586 | ||
587 | public: | |
1a4d82fc JJ |
588 | static const unsigned OverflowOccurredValue; |
589 | ||
590 | BBState() : TopDownPathCount(0), BottomUpPathCount(0) { } | |
970d7e83 LB |
591 | |
592 | typedef MapTy::iterator ptr_iterator; | |
593 | typedef MapTy::const_iterator ptr_const_iterator; | |
594 | ||
595 | ptr_iterator top_down_ptr_begin() { return PerPtrTopDown.begin(); } | |
596 | ptr_iterator top_down_ptr_end() { return PerPtrTopDown.end(); } | |
597 | ptr_const_iterator top_down_ptr_begin() const { | |
598 | return PerPtrTopDown.begin(); | |
599 | } | |
600 | ptr_const_iterator top_down_ptr_end() const { | |
601 | return PerPtrTopDown.end(); | |
602 | } | |
603 | ||
604 | ptr_iterator bottom_up_ptr_begin() { return PerPtrBottomUp.begin(); } | |
605 | ptr_iterator bottom_up_ptr_end() { return PerPtrBottomUp.end(); } | |
606 | ptr_const_iterator bottom_up_ptr_begin() const { | |
607 | return PerPtrBottomUp.begin(); | |
608 | } | |
609 | ptr_const_iterator bottom_up_ptr_end() const { | |
610 | return PerPtrBottomUp.end(); | |
611 | } | |
612 | ||
613 | /// Mark this block as being an entry block, which has one path from the | |
614 | /// entry by definition. | |
615 | void SetAsEntry() { TopDownPathCount = 1; } | |
616 | ||
617 | /// Mark this block as being an exit block, which has one path to an exit by | |
618 | /// definition. | |
619 | void SetAsExit() { BottomUpPathCount = 1; } | |
620 | ||
1a4d82fc JJ |
621 | /// Attempt to find the PtrState object describing the top down state for |
622 | /// pointer Arg. Return a new initialized PtrState describing the top down | |
623 | /// state for Arg if we do not find one. | |
970d7e83 LB |
624 | PtrState &getPtrTopDownState(const Value *Arg) { |
625 | return PerPtrTopDown[Arg]; | |
626 | } | |
627 | ||
1a4d82fc JJ |
628 | /// Attempt to find the PtrState object describing the bottom up state for |
629 | /// pointer Arg. Return a new initialized PtrState describing the bottom up | |
630 | /// state for Arg if we do not find one. | |
970d7e83 LB |
631 | PtrState &getPtrBottomUpState(const Value *Arg) { |
632 | return PerPtrBottomUp[Arg]; | |
633 | } | |
634 | ||
1a4d82fc JJ |
635 | /// Attempt to find the PtrState object describing the bottom up state for |
636 | /// pointer Arg. | |
637 | ptr_iterator findPtrBottomUpState(const Value *Arg) { | |
638 | return PerPtrBottomUp.find(Arg); | |
639 | } | |
640 | ||
970d7e83 LB |
641 | void clearBottomUpPointers() { |
642 | PerPtrBottomUp.clear(); | |
643 | } | |
644 | ||
645 | void clearTopDownPointers() { | |
646 | PerPtrTopDown.clear(); | |
647 | } | |
648 | ||
649 | void InitFromPred(const BBState &Other); | |
650 | void InitFromSucc(const BBState &Other); | |
651 | void MergePred(const BBState &Other); | |
652 | void MergeSucc(const BBState &Other); | |
653 | ||
1a4d82fc | 654 | /// Compute the number of possible unique paths from an entry to an exit |
970d7e83 LB |
655 | /// which pass through this block. This is only valid after both the |
656 | /// top-down and bottom-up traversals are complete. | |
1a4d82fc JJ |
657 | /// |
658 | /// Returns true if overflow occurred. Returns false if overflow did not | |
659 | /// occur. | |
660 | bool GetAllPathCountWithOverflow(unsigned &PathCount) const { | |
661 | if (TopDownPathCount == OverflowOccurredValue || | |
662 | BottomUpPathCount == OverflowOccurredValue) | |
663 | return true; | |
664 | unsigned long long Product = | |
665 | (unsigned long long)TopDownPathCount*BottomUpPathCount; | |
666 | // Overflow occurred if any of the upper bits of Product are set or if all | |
667 | // the lower bits of Product are all set. | |
668 | return (Product >> 32) || | |
669 | ((PathCount = Product) == OverflowOccurredValue); | |
970d7e83 LB |
670 | } |
671 | ||
672 | // Specialized CFG utilities. | |
673 | typedef SmallVectorImpl<BasicBlock *>::const_iterator edge_iterator; | |
1a4d82fc JJ |
674 | edge_iterator pred_begin() const { return Preds.begin(); } |
675 | edge_iterator pred_end() const { return Preds.end(); } | |
676 | edge_iterator succ_begin() const { return Succs.begin(); } | |
677 | edge_iterator succ_end() const { return Succs.end(); } | |
970d7e83 LB |
678 | |
679 | void addSucc(BasicBlock *Succ) { Succs.push_back(Succ); } | |
680 | void addPred(BasicBlock *Pred) { Preds.push_back(Pred); } | |
681 | ||
682 | bool isExit() const { return Succs.empty(); } | |
683 | }; | |
1a4d82fc JJ |
684 | |
685 | const unsigned BBState::OverflowOccurredValue = 0xffffffff; | |
970d7e83 LB |
686 | } |
687 | ||
688 | void BBState::InitFromPred(const BBState &Other) { | |
689 | PerPtrTopDown = Other.PerPtrTopDown; | |
690 | TopDownPathCount = Other.TopDownPathCount; | |
691 | } | |
692 | ||
693 | void BBState::InitFromSucc(const BBState &Other) { | |
694 | PerPtrBottomUp = Other.PerPtrBottomUp; | |
695 | BottomUpPathCount = Other.BottomUpPathCount; | |
696 | } | |
697 | ||
698 | /// The top-down traversal uses this to merge information about predecessors to | |
699 | /// form the initial state for a new block. | |
700 | void BBState::MergePred(const BBState &Other) { | |
1a4d82fc JJ |
701 | if (TopDownPathCount == OverflowOccurredValue) |
702 | return; | |
703 | ||
970d7e83 LB |
704 | // Other.TopDownPathCount can be 0, in which case it is either dead or a |
705 | // loop backedge. Loop backedges are special. | |
706 | TopDownPathCount += Other.TopDownPathCount; | |
707 | ||
1a4d82fc JJ |
708 | // In order to be consistent, we clear the top down pointers when by adding |
709 | // TopDownPathCount becomes OverflowOccurredValue even though "true" overflow | |
710 | // has not occurred. | |
711 | if (TopDownPathCount == OverflowOccurredValue) { | |
712 | clearTopDownPointers(); | |
713 | return; | |
714 | } | |
715 | ||
970d7e83 LB |
716 | // Check for overflow. If we have overflow, fall back to conservative |
717 | // behavior. | |
718 | if (TopDownPathCount < Other.TopDownPathCount) { | |
1a4d82fc | 719 | TopDownPathCount = OverflowOccurredValue; |
970d7e83 LB |
720 | clearTopDownPointers(); |
721 | return; | |
722 | } | |
723 | ||
724 | // For each entry in the other set, if our set has an entry with the same key, | |
725 | // merge the entries. Otherwise, copy the entry and merge it with an empty | |
726 | // entry. | |
727 | for (ptr_const_iterator MI = Other.top_down_ptr_begin(), | |
728 | ME = Other.top_down_ptr_end(); MI != ME; ++MI) { | |
729 | std::pair<ptr_iterator, bool> Pair = PerPtrTopDown.insert(*MI); | |
730 | Pair.first->second.Merge(Pair.second ? PtrState() : MI->second, | |
731 | /*TopDown=*/true); | |
732 | } | |
733 | ||
734 | // For each entry in our set, if the other set doesn't have an entry with the | |
735 | // same key, force it to merge with an empty entry. | |
736 | for (ptr_iterator MI = top_down_ptr_begin(), | |
737 | ME = top_down_ptr_end(); MI != ME; ++MI) | |
738 | if (Other.PerPtrTopDown.find(MI->first) == Other.PerPtrTopDown.end()) | |
739 | MI->second.Merge(PtrState(), /*TopDown=*/true); | |
740 | } | |
741 | ||
742 | /// The bottom-up traversal uses this to merge information about successors to | |
743 | /// form the initial state for a new block. | |
744 | void BBState::MergeSucc(const BBState &Other) { | |
1a4d82fc JJ |
745 | if (BottomUpPathCount == OverflowOccurredValue) |
746 | return; | |
747 | ||
970d7e83 LB |
748 | // Other.BottomUpPathCount can be 0, in which case it is either dead or a |
749 | // loop backedge. Loop backedges are special. | |
750 | BottomUpPathCount += Other.BottomUpPathCount; | |
751 | ||
1a4d82fc JJ |
752 | // In order to be consistent, we clear the top down pointers when by adding |
753 | // BottomUpPathCount becomes OverflowOccurredValue even though "true" overflow | |
754 | // has not occurred. | |
755 | if (BottomUpPathCount == OverflowOccurredValue) { | |
756 | clearBottomUpPointers(); | |
757 | return; | |
758 | } | |
759 | ||
970d7e83 LB |
760 | // Check for overflow. If we have overflow, fall back to conservative |
761 | // behavior. | |
762 | if (BottomUpPathCount < Other.BottomUpPathCount) { | |
1a4d82fc | 763 | BottomUpPathCount = OverflowOccurredValue; |
970d7e83 LB |
764 | clearBottomUpPointers(); |
765 | return; | |
766 | } | |
767 | ||
768 | // For each entry in the other set, if our set has an entry with the | |
769 | // same key, merge the entries. Otherwise, copy the entry and merge | |
770 | // it with an empty entry. | |
771 | for (ptr_const_iterator MI = Other.bottom_up_ptr_begin(), | |
772 | ME = Other.bottom_up_ptr_end(); MI != ME; ++MI) { | |
773 | std::pair<ptr_iterator, bool> Pair = PerPtrBottomUp.insert(*MI); | |
774 | Pair.first->second.Merge(Pair.second ? PtrState() : MI->second, | |
775 | /*TopDown=*/false); | |
776 | } | |
777 | ||
778 | // For each entry in our set, if the other set doesn't have an entry | |
779 | // with the same key, force it to merge with an empty entry. | |
780 | for (ptr_iterator MI = bottom_up_ptr_begin(), | |
781 | ME = bottom_up_ptr_end(); MI != ME; ++MI) | |
782 | if (Other.PerPtrBottomUp.find(MI->first) == Other.PerPtrBottomUp.end()) | |
783 | MI->second.Merge(PtrState(), /*TopDown=*/false); | |
784 | } | |
785 | ||
1a4d82fc JJ |
786 | // Only enable ARC Annotations if we are building a debug version of |
787 | // libObjCARCOpts. | |
788 | #ifndef NDEBUG | |
789 | #define ARC_ANNOTATIONS | |
790 | #endif | |
791 | ||
792 | // Define some macros along the lines of DEBUG and some helper functions to make | |
793 | // it cleaner to create annotations in the source code and to no-op when not | |
794 | // building in debug mode. | |
795 | #ifdef ARC_ANNOTATIONS | |
796 | ||
797 | #include "llvm/Support/CommandLine.h" | |
798 | ||
799 | /// Enable/disable ARC sequence annotations. | |
800 | static cl::opt<bool> | |
801 | EnableARCAnnotations("enable-objc-arc-annotations", cl::init(false), | |
802 | cl::desc("Enable emission of arc data flow analysis " | |
803 | "annotations")); | |
804 | static cl::opt<bool> | |
805 | DisableCheckForCFGHazards("disable-objc-arc-checkforcfghazards", cl::init(false), | |
806 | cl::desc("Disable check for cfg hazards when " | |
807 | "annotating")); | |
808 | static cl::opt<std::string> | |
809 | ARCAnnotationTargetIdentifier("objc-arc-annotation-target-identifier", | |
810 | cl::init(""), | |
811 | cl::desc("filter out all data flow annotations " | |
812 | "but those that apply to the given " | |
813 | "target llvm identifier.")); | |
814 | ||
815 | /// This function appends a unique ARCAnnotationProvenanceSourceMDKind id to an | |
816 | /// instruction so that we can track backwards when post processing via the llvm | |
817 | /// arc annotation processor tool. If the function is an | |
818 | static MDString *AppendMDNodeToSourcePtr(unsigned NodeId, | |
819 | Value *Ptr) { | |
820 | MDString *Hash = nullptr; | |
821 | ||
822 | // If pointer is a result of an instruction and it does not have a source | |
823 | // MDNode it, attach a new MDNode onto it. If pointer is a result of | |
824 | // an instruction and does have a source MDNode attached to it, return a | |
825 | // reference to said Node. Otherwise just return 0. | |
826 | if (Instruction *Inst = dyn_cast<Instruction>(Ptr)) { | |
827 | MDNode *Node; | |
828 | if (!(Node = Inst->getMetadata(NodeId))) { | |
829 | // We do not have any node. Generate and attatch the hash MDString to the | |
830 | // instruction. | |
831 | ||
832 | // We just use an MDString to ensure that this metadata gets written out | |
833 | // of line at the module level and to provide a very simple format | |
834 | // encoding the information herein. Both of these makes it simpler to | |
835 | // parse the annotations by a simple external program. | |
836 | std::string Str; | |
837 | raw_string_ostream os(Str); | |
838 | os << "(" << Inst->getParent()->getParent()->getName() << ",%" | |
839 | << Inst->getName() << ")"; | |
840 | ||
841 | Hash = MDString::get(Inst->getContext(), os.str()); | |
842 | Inst->setMetadata(NodeId, MDNode::get(Inst->getContext(),Hash)); | |
843 | } else { | |
844 | // We have a node. Grab its hash and return it. | |
845 | assert(Node->getNumOperands() == 1 && | |
846 | "An ARCAnnotationProvenanceSourceMDKind can only have 1 operand."); | |
847 | Hash = cast<MDString>(Node->getOperand(0)); | |
848 | } | |
849 | } else if (Argument *Arg = dyn_cast<Argument>(Ptr)) { | |
850 | std::string str; | |
851 | raw_string_ostream os(str); | |
852 | os << "(" << Arg->getParent()->getName() << ",%" << Arg->getName() | |
853 | << ")"; | |
854 | Hash = MDString::get(Arg->getContext(), os.str()); | |
855 | } | |
856 | ||
857 | return Hash; | |
858 | } | |
859 | ||
860 | static std::string SequenceToString(Sequence A) { | |
861 | std::string str; | |
862 | raw_string_ostream os(str); | |
863 | os << A; | |
864 | return os.str(); | |
865 | } | |
866 | ||
867 | /// Helper function to change a Sequence into a String object using our overload | |
868 | /// for raw_ostream so we only have printing code in one location. | |
869 | static MDString *SequenceToMDString(LLVMContext &Context, | |
870 | Sequence A) { | |
871 | return MDString::get(Context, SequenceToString(A)); | |
872 | } | |
873 | ||
874 | /// A simple function to generate a MDNode which describes the change in state | |
875 | /// for Value *Ptr caused by Instruction *Inst. | |
876 | static void AppendMDNodeToInstForPtr(unsigned NodeId, | |
877 | Instruction *Inst, | |
878 | Value *Ptr, | |
879 | MDString *PtrSourceMDNodeID, | |
880 | Sequence OldSeq, | |
881 | Sequence NewSeq) { | |
882 | MDNode *Node = nullptr; | |
85aaf69f SL |
883 | Metadata *tmp[3] = {PtrSourceMDNodeID, |
884 | SequenceToMDString(Inst->getContext(), OldSeq), | |
885 | SequenceToMDString(Inst->getContext(), NewSeq)}; | |
1a4d82fc JJ |
886 | Node = MDNode::get(Inst->getContext(), tmp); |
887 | ||
888 | Inst->setMetadata(NodeId, Node); | |
889 | } | |
890 | ||
891 | /// Add to the beginning of the basic block llvm.ptr.annotations which show the | |
892 | /// state of a pointer at the entrance to a basic block. | |
893 | static void GenerateARCBBEntranceAnnotation(const char *Name, BasicBlock *BB, | |
894 | Value *Ptr, Sequence Seq) { | |
895 | // If we have a target identifier, make sure that we match it before | |
896 | // continuing. | |
897 | if(!ARCAnnotationTargetIdentifier.empty() && | |
898 | !Ptr->getName().equals(ARCAnnotationTargetIdentifier)) | |
899 | return; | |
900 | ||
901 | Module *M = BB->getParent()->getParent(); | |
902 | LLVMContext &C = M->getContext(); | |
903 | Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C)); | |
904 | Type *I8XX = PointerType::getUnqual(I8X); | |
905 | Type *Params[] = {I8XX, I8XX}; | |
906 | FunctionType *FTy = FunctionType::get(Type::getVoidTy(C), Params, | |
907 | /*isVarArg=*/false); | |
908 | Constant *Callee = M->getOrInsertFunction(Name, FTy); | |
909 | ||
910 | IRBuilder<> Builder(BB, BB->getFirstInsertionPt()); | |
911 | ||
912 | Value *PtrName; | |
913 | StringRef Tmp = Ptr->getName(); | |
914 | if (nullptr == (PtrName = M->getGlobalVariable(Tmp, true))) { | |
915 | Value *ActualPtrName = Builder.CreateGlobalStringPtr(Tmp, | |
916 | Tmp + "_STR"); | |
917 | PtrName = new GlobalVariable(*M, I8X, true, GlobalVariable::InternalLinkage, | |
918 | cast<Constant>(ActualPtrName), Tmp); | |
919 | } | |
920 | ||
921 | Value *S; | |
922 | std::string SeqStr = SequenceToString(Seq); | |
923 | if (nullptr == (S = M->getGlobalVariable(SeqStr, true))) { | |
924 | Value *ActualPtrName = Builder.CreateGlobalStringPtr(SeqStr, | |
925 | SeqStr + "_STR"); | |
926 | S = new GlobalVariable(*M, I8X, true, GlobalVariable::InternalLinkage, | |
927 | cast<Constant>(ActualPtrName), SeqStr); | |
928 | } | |
929 | ||
930 | Builder.CreateCall2(Callee, PtrName, S); | |
931 | } | |
932 | ||
933 | /// Add to the end of the basic block llvm.ptr.annotations which show the state | |
934 | /// of the pointer at the bottom of the basic block. | |
935 | static void GenerateARCBBTerminatorAnnotation(const char *Name, BasicBlock *BB, | |
936 | Value *Ptr, Sequence Seq) { | |
937 | // If we have a target identifier, make sure that we match it before emitting | |
938 | // an annotation. | |
939 | if(!ARCAnnotationTargetIdentifier.empty() && | |
940 | !Ptr->getName().equals(ARCAnnotationTargetIdentifier)) | |
941 | return; | |
942 | ||
943 | Module *M = BB->getParent()->getParent(); | |
944 | LLVMContext &C = M->getContext(); | |
945 | Type *I8X = PointerType::getUnqual(Type::getInt8Ty(C)); | |
946 | Type *I8XX = PointerType::getUnqual(I8X); | |
947 | Type *Params[] = {I8XX, I8XX}; | |
948 | FunctionType *FTy = FunctionType::get(Type::getVoidTy(C), Params, | |
949 | /*isVarArg=*/false); | |
950 | Constant *Callee = M->getOrInsertFunction(Name, FTy); | |
951 | ||
952 | IRBuilder<> Builder(BB, std::prev(BB->end())); | |
953 | ||
954 | Value *PtrName; | |
955 | StringRef Tmp = Ptr->getName(); | |
956 | if (nullptr == (PtrName = M->getGlobalVariable(Tmp, true))) { | |
957 | Value *ActualPtrName = Builder.CreateGlobalStringPtr(Tmp, | |
958 | Tmp + "_STR"); | |
959 | PtrName = new GlobalVariable(*M, I8X, true, GlobalVariable::InternalLinkage, | |
960 | cast<Constant>(ActualPtrName), Tmp); | |
961 | } | |
962 | ||
963 | Value *S; | |
964 | std::string SeqStr = SequenceToString(Seq); | |
965 | if (nullptr == (S = M->getGlobalVariable(SeqStr, true))) { | |
966 | Value *ActualPtrName = Builder.CreateGlobalStringPtr(SeqStr, | |
967 | SeqStr + "_STR"); | |
968 | S = new GlobalVariable(*M, I8X, true, GlobalVariable::InternalLinkage, | |
969 | cast<Constant>(ActualPtrName), SeqStr); | |
970 | } | |
971 | Builder.CreateCall2(Callee, PtrName, S); | |
972 | } | |
973 | ||
974 | /// Adds a source annotation to pointer and a state change annotation to Inst | |
975 | /// referencing the source annotation and the old/new state of pointer. | |
976 | static void GenerateARCAnnotation(unsigned InstMDId, | |
977 | unsigned PtrMDId, | |
978 | Instruction *Inst, | |
979 | Value *Ptr, | |
980 | Sequence OldSeq, | |
981 | Sequence NewSeq) { | |
982 | if (EnableARCAnnotations) { | |
983 | // If we have a target identifier, make sure that we match it before | |
984 | // emitting an annotation. | |
985 | if(!ARCAnnotationTargetIdentifier.empty() && | |
986 | !Ptr->getName().equals(ARCAnnotationTargetIdentifier)) | |
987 | return; | |
988 | ||
989 | // First generate the source annotation on our pointer. This will return an | |
990 | // MDString* if Ptr actually comes from an instruction implying we can put | |
991 | // in a source annotation. If AppendMDNodeToSourcePtr returns 0 (i.e. NULL), | |
992 | // then we know that our pointer is from an Argument so we put a reference | |
993 | // to the argument number. | |
994 | // | |
995 | // The point of this is to make it easy for the | |
996 | // llvm-arc-annotation-processor tool to cross reference where the source | |
997 | // pointer is in the LLVM IR since the LLVM IR parser does not submit such | |
998 | // information via debug info for backends to use (since why would anyone | |
999 | // need such a thing from LLVM IR besides in non-standard cases | |
1000 | // [i.e. this]). | |
1001 | MDString *SourcePtrMDNode = | |
1002 | AppendMDNodeToSourcePtr(PtrMDId, Ptr); | |
1003 | AppendMDNodeToInstForPtr(InstMDId, Inst, Ptr, SourcePtrMDNode, OldSeq, | |
1004 | NewSeq); | |
1005 | } | |
1006 | } | |
1007 | ||
1008 | // The actual interface for accessing the above functionality is defined via | |
1009 | // some simple macros which are defined below. We do this so that the user does | |
1010 | // not need to pass in what metadata id is needed resulting in cleaner code and | |
1011 | // additionally since it provides an easy way to conditionally no-op all | |
1012 | // annotation support in a non-debug build. | |
1013 | ||
1014 | /// Use this macro to annotate a sequence state change when processing | |
1015 | /// instructions bottom up, | |
1016 | #define ANNOTATE_BOTTOMUP(inst, ptr, old, new) \ | |
1017 | GenerateARCAnnotation(ARCAnnotationBottomUpMDKind, \ | |
1018 | ARCAnnotationProvenanceSourceMDKind, (inst), \ | |
1019 | const_cast<Value*>(ptr), (old), (new)) | |
1020 | /// Use this macro to annotate a sequence state change when processing | |
1021 | /// instructions top down. | |
1022 | #define ANNOTATE_TOPDOWN(inst, ptr, old, new) \ | |
1023 | GenerateARCAnnotation(ARCAnnotationTopDownMDKind, \ | |
1024 | ARCAnnotationProvenanceSourceMDKind, (inst), \ | |
1025 | const_cast<Value*>(ptr), (old), (new)) | |
1026 | ||
1027 | #define ANNOTATE_BB(_states, _bb, _name, _type, _direction) \ | |
1028 | do { \ | |
1029 | if (EnableARCAnnotations) { \ | |
1030 | for(BBState::ptr_const_iterator I = (_states)._direction##_ptr_begin(), \ | |
1031 | E = (_states)._direction##_ptr_end(); I != E; ++I) { \ | |
1032 | Value *Ptr = const_cast<Value*>(I->first); \ | |
1033 | Sequence Seq = I->second.GetSeq(); \ | |
1034 | GenerateARCBB ## _type ## Annotation(_name, (_bb), Ptr, Seq); \ | |
1035 | } \ | |
1036 | } \ | |
1037 | } while (0) | |
1038 | ||
1039 | #define ANNOTATE_BOTTOMUP_BBSTART(_states, _basicblock) \ | |
1040 | ANNOTATE_BB(_states, _basicblock, "llvm.arc.annotation.bottomup.bbstart", \ | |
1041 | Entrance, bottom_up) | |
1042 | #define ANNOTATE_BOTTOMUP_BBEND(_states, _basicblock) \ | |
1043 | ANNOTATE_BB(_states, _basicblock, "llvm.arc.annotation.bottomup.bbend", \ | |
1044 | Terminator, bottom_up) | |
1045 | #define ANNOTATE_TOPDOWN_BBSTART(_states, _basicblock) \ | |
1046 | ANNOTATE_BB(_states, _basicblock, "llvm.arc.annotation.topdown.bbstart", \ | |
1047 | Entrance, top_down) | |
1048 | #define ANNOTATE_TOPDOWN_BBEND(_states, _basicblock) \ | |
1049 | ANNOTATE_BB(_states, _basicblock, "llvm.arc.annotation.topdown.bbend", \ | |
1050 | Terminator, top_down) | |
1051 | ||
1052 | #else // !ARC_ANNOTATION | |
1053 | // If annotations are off, noop. | |
1054 | #define ANNOTATE_BOTTOMUP(inst, ptr, old, new) | |
1055 | #define ANNOTATE_TOPDOWN(inst, ptr, old, new) | |
1056 | #define ANNOTATE_BOTTOMUP_BBSTART(states, basicblock) | |
1057 | #define ANNOTATE_BOTTOMUP_BBEND(states, basicblock) | |
1058 | #define ANNOTATE_TOPDOWN_BBSTART(states, basicblock) | |
1059 | #define ANNOTATE_TOPDOWN_BBEND(states, basicblock) | |
1060 | #endif // !ARC_ANNOTATION | |
1061 | ||
970d7e83 LB |
1062 | namespace { |
1063 | /// \brief The main ARC optimization pass. | |
1064 | class ObjCARCOpt : public FunctionPass { | |
1065 | bool Changed; | |
1066 | ProvenanceAnalysis PA; | |
1a4d82fc JJ |
1067 | ARCRuntimeEntryPoints EP; |
1068 | ||
1069 | // This is used to track if a pointer is stored into an alloca. | |
1070 | DenseSet<const Value *> MultiOwnersSet; | |
970d7e83 LB |
1071 | |
1072 | /// A flag indicating whether this optimization pass should run. | |
1073 | bool Run; | |
1074 | ||
970d7e83 LB |
1075 | /// Flags which determine whether each of the interesting runtine functions |
1076 | /// is in fact used in the current function. | |
1077 | unsigned UsedInThisFunction; | |
1078 | ||
1079 | /// The Metadata Kind for clang.imprecise_release metadata. | |
1080 | unsigned ImpreciseReleaseMDKind; | |
1081 | ||
1082 | /// The Metadata Kind for clang.arc.copy_on_escape metadata. | |
1083 | unsigned CopyOnEscapeMDKind; | |
1084 | ||
1085 | /// The Metadata Kind for clang.arc.no_objc_arc_exceptions metadata. | |
1086 | unsigned NoObjCARCExceptionsMDKind; | |
1087 | ||
1a4d82fc JJ |
1088 | #ifdef ARC_ANNOTATIONS |
1089 | /// The Metadata Kind for llvm.arc.annotation.bottomup metadata. | |
1090 | unsigned ARCAnnotationBottomUpMDKind; | |
1091 | /// The Metadata Kind for llvm.arc.annotation.topdown metadata. | |
1092 | unsigned ARCAnnotationTopDownMDKind; | |
1093 | /// The Metadata Kind for llvm.arc.annotation.provenancesource metadata. | |
1094 | unsigned ARCAnnotationProvenanceSourceMDKind; | |
1095 | #endif // ARC_ANNOATIONS | |
970d7e83 | 1096 | |
970d7e83 LB |
1097 | bool OptimizeRetainRVCall(Function &F, Instruction *RetainRV); |
1098 | void OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV, | |
1099 | InstructionClass &Class); | |
1100 | void OptimizeIndividualCalls(Function &F); | |
1101 | ||
1102 | void CheckForCFGHazards(const BasicBlock *BB, | |
1103 | DenseMap<const BasicBlock *, BBState> &BBStates, | |
1104 | BBState &MyStates) const; | |
1105 | bool VisitInstructionBottomUp(Instruction *Inst, | |
1106 | BasicBlock *BB, | |
1107 | MapVector<Value *, RRInfo> &Retains, | |
1108 | BBState &MyStates); | |
1109 | bool VisitBottomUp(BasicBlock *BB, | |
1110 | DenseMap<const BasicBlock *, BBState> &BBStates, | |
1111 | MapVector<Value *, RRInfo> &Retains); | |
1112 | bool VisitInstructionTopDown(Instruction *Inst, | |
1113 | DenseMap<Value *, RRInfo> &Releases, | |
1114 | BBState &MyStates); | |
1115 | bool VisitTopDown(BasicBlock *BB, | |
1116 | DenseMap<const BasicBlock *, BBState> &BBStates, | |
1117 | DenseMap<Value *, RRInfo> &Releases); | |
1118 | bool Visit(Function &F, | |
1119 | DenseMap<const BasicBlock *, BBState> &BBStates, | |
1120 | MapVector<Value *, RRInfo> &Retains, | |
1121 | DenseMap<Value *, RRInfo> &Releases); | |
1122 | ||
1123 | void MoveCalls(Value *Arg, RRInfo &RetainsToMove, RRInfo &ReleasesToMove, | |
1124 | MapVector<Value *, RRInfo> &Retains, | |
1125 | DenseMap<Value *, RRInfo> &Releases, | |
1126 | SmallVectorImpl<Instruction *> &DeadInsts, | |
1127 | Module *M); | |
1128 | ||
1129 | bool ConnectTDBUTraversals(DenseMap<const BasicBlock *, BBState> &BBStates, | |
1130 | MapVector<Value *, RRInfo> &Retains, | |
1131 | DenseMap<Value *, RRInfo> &Releases, | |
1132 | Module *M, | |
1a4d82fc JJ |
1133 | SmallVectorImpl<Instruction *> &NewRetains, |
1134 | SmallVectorImpl<Instruction *> &NewReleases, | |
1135 | SmallVectorImpl<Instruction *> &DeadInsts, | |
970d7e83 LB |
1136 | RRInfo &RetainsToMove, |
1137 | RRInfo &ReleasesToMove, | |
1138 | Value *Arg, | |
1139 | bool KnownSafe, | |
1140 | bool &AnyPairsCompletelyEliminated); | |
1141 | ||
1142 | bool PerformCodePlacement(DenseMap<const BasicBlock *, BBState> &BBStates, | |
1143 | MapVector<Value *, RRInfo> &Retains, | |
1144 | DenseMap<Value *, RRInfo> &Releases, | |
1145 | Module *M); | |
1146 | ||
1147 | void OptimizeWeakCalls(Function &F); | |
1148 | ||
1149 | bool OptimizeSequences(Function &F); | |
1150 | ||
1151 | void OptimizeReturns(Function &F); | |
1152 | ||
1a4d82fc JJ |
1153 | #ifndef NDEBUG |
1154 | void GatherStatistics(Function &F, bool AfterOptimization = false); | |
1155 | #endif | |
1156 | ||
1157 | void getAnalysisUsage(AnalysisUsage &AU) const override; | |
1158 | bool doInitialization(Module &M) override; | |
1159 | bool runOnFunction(Function &F) override; | |
1160 | void releaseMemory() override; | |
970d7e83 LB |
1161 | |
1162 | public: | |
1163 | static char ID; | |
1164 | ObjCARCOpt() : FunctionPass(ID) { | |
1165 | initializeObjCARCOptPass(*PassRegistry::getPassRegistry()); | |
1166 | } | |
1167 | }; | |
1168 | } | |
1169 | ||
1170 | char ObjCARCOpt::ID = 0; | |
1171 | INITIALIZE_PASS_BEGIN(ObjCARCOpt, | |
1172 | "objc-arc", "ObjC ARC optimization", false, false) | |
1173 | INITIALIZE_PASS_DEPENDENCY(ObjCARCAliasAnalysis) | |
1174 | INITIALIZE_PASS_END(ObjCARCOpt, | |
1175 | "objc-arc", "ObjC ARC optimization", false, false) | |
1176 | ||
1177 | Pass *llvm::createObjCARCOptPass() { | |
1178 | return new ObjCARCOpt(); | |
1179 | } | |
1180 | ||
1181 | void ObjCARCOpt::getAnalysisUsage(AnalysisUsage &AU) const { | |
1182 | AU.addRequired<ObjCARCAliasAnalysis>(); | |
1183 | AU.addRequired<AliasAnalysis>(); | |
1184 | // ARC optimization doesn't currently split critical edges. | |
1185 | AU.setPreservesCFG(); | |
1186 | } | |
1187 | ||
970d7e83 LB |
1188 | /// Turn objc_retainAutoreleasedReturnValue into objc_retain if the operand is |
1189 | /// not a return value. Or, if it can be paired with an | |
1190 | /// objc_autoreleaseReturnValue, delete the pair and return true. | |
1191 | bool | |
1192 | ObjCARCOpt::OptimizeRetainRVCall(Function &F, Instruction *RetainRV) { | |
1193 | // Check for the argument being from an immediately preceding call or invoke. | |
1194 | const Value *Arg = GetObjCArg(RetainRV); | |
1195 | ImmutableCallSite CS(Arg); | |
1196 | if (const Instruction *Call = CS.getInstruction()) { | |
1197 | if (Call->getParent() == RetainRV->getParent()) { | |
1198 | BasicBlock::const_iterator I = Call; | |
1199 | ++I; | |
1a4d82fc | 1200 | while (IsNoopInstruction(I)) ++I; |
970d7e83 LB |
1201 | if (&*I == RetainRV) |
1202 | return false; | |
1203 | } else if (const InvokeInst *II = dyn_cast<InvokeInst>(Call)) { | |
1204 | BasicBlock *RetainRVParent = RetainRV->getParent(); | |
1205 | if (II->getNormalDest() == RetainRVParent) { | |
1206 | BasicBlock::const_iterator I = RetainRVParent->begin(); | |
1a4d82fc | 1207 | while (IsNoopInstruction(I)) ++I; |
970d7e83 LB |
1208 | if (&*I == RetainRV) |
1209 | return false; | |
1210 | } | |
1211 | } | |
1212 | } | |
1213 | ||
1214 | // Check for being preceded by an objc_autoreleaseReturnValue on the same | |
1215 | // pointer. In this case, we can delete the pair. | |
1216 | BasicBlock::iterator I = RetainRV, Begin = RetainRV->getParent()->begin(); | |
1217 | if (I != Begin) { | |
1a4d82fc | 1218 | do --I; while (I != Begin && IsNoopInstruction(I)); |
970d7e83 LB |
1219 | if (GetBasicInstructionClass(I) == IC_AutoreleaseRV && |
1220 | GetObjCArg(I) == Arg) { | |
1221 | Changed = true; | |
1222 | ++NumPeeps; | |
1223 | ||
1a4d82fc JJ |
1224 | DEBUG(dbgs() << "Erasing autoreleaseRV,retainRV pair: " << *I << "\n" |
1225 | << "Erasing " << *RetainRV << "\n"); | |
970d7e83 LB |
1226 | |
1227 | EraseInstruction(I); | |
1228 | EraseInstruction(RetainRV); | |
1229 | return true; | |
1230 | } | |
1231 | } | |
1232 | ||
1233 | // Turn it to a plain objc_retain. | |
1234 | Changed = true; | |
1235 | ++NumPeeps; | |
1236 | ||
1a4d82fc | 1237 | DEBUG(dbgs() << "Transforming objc_retainAutoreleasedReturnValue => " |
970d7e83 | 1238 | "objc_retain since the operand is not a return value.\n" |
1a4d82fc | 1239 | "Old = " << *RetainRV << "\n"); |
970d7e83 | 1240 | |
1a4d82fc JJ |
1241 | Constant *NewDecl = EP.get(ARCRuntimeEntryPoints::EPT_Retain); |
1242 | cast<CallInst>(RetainRV)->setCalledFunction(NewDecl); | |
970d7e83 | 1243 | |
1a4d82fc | 1244 | DEBUG(dbgs() << "New = " << *RetainRV << "\n"); |
970d7e83 LB |
1245 | |
1246 | return false; | |
1247 | } | |
1248 | ||
1249 | /// Turn objc_autoreleaseReturnValue into objc_autorelease if the result is not | |
1250 | /// used as a return value. | |
1251 | void | |
1252 | ObjCARCOpt::OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV, | |
1253 | InstructionClass &Class) { | |
1254 | // Check for a return of the pointer value. | |
1255 | const Value *Ptr = GetObjCArg(AutoreleaseRV); | |
1256 | SmallVector<const Value *, 2> Users; | |
1257 | Users.push_back(Ptr); | |
1258 | do { | |
1259 | Ptr = Users.pop_back_val(); | |
1a4d82fc JJ |
1260 | for (const User *U : Ptr->users()) { |
1261 | if (isa<ReturnInst>(U) || GetBasicInstructionClass(U) == IC_RetainRV) | |
970d7e83 | 1262 | return; |
1a4d82fc JJ |
1263 | if (isa<BitCastInst>(U)) |
1264 | Users.push_back(U); | |
970d7e83 LB |
1265 | } |
1266 | } while (!Users.empty()); | |
1267 | ||
1268 | Changed = true; | |
1269 | ++NumPeeps; | |
1270 | ||
1a4d82fc | 1271 | DEBUG(dbgs() << "Transforming objc_autoreleaseReturnValue => " |
970d7e83 LB |
1272 | "objc_autorelease since its operand is not used as a return " |
1273 | "value.\n" | |
1a4d82fc | 1274 | "Old = " << *AutoreleaseRV << "\n"); |
970d7e83 LB |
1275 | |
1276 | CallInst *AutoreleaseRVCI = cast<CallInst>(AutoreleaseRV); | |
1a4d82fc JJ |
1277 | Constant *NewDecl = EP.get(ARCRuntimeEntryPoints::EPT_Autorelease); |
1278 | AutoreleaseRVCI->setCalledFunction(NewDecl); | |
970d7e83 LB |
1279 | AutoreleaseRVCI->setTailCall(false); // Never tail call objc_autorelease. |
1280 | Class = IC_Autorelease; | |
1281 | ||
1a4d82fc | 1282 | DEBUG(dbgs() << "New: " << *AutoreleaseRV << "\n"); |
970d7e83 LB |
1283 | |
1284 | } | |
1285 | ||
1286 | /// Visit each call, one at a time, and make simplifications without doing any | |
1287 | /// additional analysis. | |
1288 | void ObjCARCOpt::OptimizeIndividualCalls(Function &F) { | |
1a4d82fc | 1289 | DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeIndividualCalls ==\n"); |
970d7e83 LB |
1290 | // Reset all the flags in preparation for recomputing them. |
1291 | UsedInThisFunction = 0; | |
1292 | ||
1293 | // Visit all objc_* calls in F. | |
1294 | for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) { | |
1295 | Instruction *Inst = &*I++; | |
1296 | ||
1297 | InstructionClass Class = GetBasicInstructionClass(Inst); | |
1298 | ||
1a4d82fc | 1299 | DEBUG(dbgs() << "Visiting: Class: " << Class << "; " << *Inst << "\n"); |
970d7e83 LB |
1300 | |
1301 | switch (Class) { | |
1302 | default: break; | |
1303 | ||
1304 | // Delete no-op casts. These function calls have special semantics, but | |
1305 | // the semantics are entirely implemented via lowering in the front-end, | |
1306 | // so by the time they reach the optimizer, they are just no-op calls | |
1307 | // which return their argument. | |
1308 | // | |
1309 | // There are gray areas here, as the ability to cast reference-counted | |
1310 | // pointers to raw void* and back allows code to break ARC assumptions, | |
1311 | // however these are currently considered to be unimportant. | |
1312 | case IC_NoopCast: | |
1313 | Changed = true; | |
1314 | ++NumNoops; | |
1a4d82fc | 1315 | DEBUG(dbgs() << "Erasing no-op cast: " << *Inst << "\n"); |
970d7e83 LB |
1316 | EraseInstruction(Inst); |
1317 | continue; | |
1318 | ||
1319 | // If the pointer-to-weak-pointer is null, it's undefined behavior. | |
1320 | case IC_StoreWeak: | |
1321 | case IC_LoadWeak: | |
1322 | case IC_LoadWeakRetained: | |
1323 | case IC_InitWeak: | |
1324 | case IC_DestroyWeak: { | |
1325 | CallInst *CI = cast<CallInst>(Inst); | |
1a4d82fc | 1326 | if (IsNullOrUndef(CI->getArgOperand(0))) { |
970d7e83 LB |
1327 | Changed = true; |
1328 | Type *Ty = CI->getArgOperand(0)->getType(); | |
1329 | new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()), | |
1330 | Constant::getNullValue(Ty), | |
1331 | CI); | |
1332 | llvm::Value *NewValue = UndefValue::get(CI->getType()); | |
1a4d82fc JJ |
1333 | DEBUG(dbgs() << "A null pointer-to-weak-pointer is undefined behavior." |
1334 | "\nOld = " << *CI << "\nNew = " << *NewValue << "\n"); | |
970d7e83 LB |
1335 | CI->replaceAllUsesWith(NewValue); |
1336 | CI->eraseFromParent(); | |
1337 | continue; | |
1338 | } | |
1339 | break; | |
1340 | } | |
1341 | case IC_CopyWeak: | |
1342 | case IC_MoveWeak: { | |
1343 | CallInst *CI = cast<CallInst>(Inst); | |
1a4d82fc JJ |
1344 | if (IsNullOrUndef(CI->getArgOperand(0)) || |
1345 | IsNullOrUndef(CI->getArgOperand(1))) { | |
970d7e83 LB |
1346 | Changed = true; |
1347 | Type *Ty = CI->getArgOperand(0)->getType(); | |
1348 | new StoreInst(UndefValue::get(cast<PointerType>(Ty)->getElementType()), | |
1349 | Constant::getNullValue(Ty), | |
1350 | CI); | |
1351 | ||
1352 | llvm::Value *NewValue = UndefValue::get(CI->getType()); | |
1a4d82fc JJ |
1353 | DEBUG(dbgs() << "A null pointer-to-weak-pointer is undefined behavior." |
1354 | "\nOld = " << *CI << "\nNew = " << *NewValue << "\n"); | |
970d7e83 LB |
1355 | |
1356 | CI->replaceAllUsesWith(NewValue); | |
1357 | CI->eraseFromParent(); | |
1358 | continue; | |
1359 | } | |
1360 | break; | |
1361 | } | |
970d7e83 LB |
1362 | case IC_RetainRV: |
1363 | if (OptimizeRetainRVCall(F, Inst)) | |
1364 | continue; | |
1365 | break; | |
1366 | case IC_AutoreleaseRV: | |
1367 | OptimizeAutoreleaseRVCall(F, Inst, Class); | |
1368 | break; | |
1369 | } | |
1370 | ||
1371 | // objc_autorelease(x) -> objc_release(x) if x is otherwise unused. | |
1372 | if (IsAutorelease(Class) && Inst->use_empty()) { | |
1373 | CallInst *Call = cast<CallInst>(Inst); | |
1374 | const Value *Arg = Call->getArgOperand(0); | |
1375 | Arg = FindSingleUseIdentifiedObject(Arg); | |
1376 | if (Arg) { | |
1377 | Changed = true; | |
1378 | ++NumAutoreleases; | |
1379 | ||
1380 | // Create the declaration lazily. | |
1381 | LLVMContext &C = Inst->getContext(); | |
1a4d82fc JJ |
1382 | |
1383 | Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_Release); | |
1384 | CallInst *NewCall = CallInst::Create(Decl, Call->getArgOperand(0), "", | |
1385 | Call); | |
1386 | NewCall->setMetadata(ImpreciseReleaseMDKind, MDNode::get(C, None)); | |
1387 | ||
1388 | DEBUG(dbgs() << "Replacing autorelease{,RV}(x) with objc_release(x) " | |
1389 | "since x is otherwise unused.\nOld: " << *Call << "\nNew: " | |
1390 | << *NewCall << "\n"); | |
970d7e83 LB |
1391 | |
1392 | EraseInstruction(Call); | |
1393 | Inst = NewCall; | |
1394 | Class = IC_Release; | |
1395 | } | |
1396 | } | |
1397 | ||
1398 | // For functions which can never be passed stack arguments, add | |
1399 | // a tail keyword. | |
1400 | if (IsAlwaysTail(Class)) { | |
1401 | Changed = true; | |
1a4d82fc JJ |
1402 | DEBUG(dbgs() << "Adding tail keyword to function since it can never be " |
1403 | "passed stack args: " << *Inst << "\n"); | |
970d7e83 LB |
1404 | cast<CallInst>(Inst)->setTailCall(); |
1405 | } | |
1406 | ||
1407 | // Ensure that functions that can never have a "tail" keyword due to the | |
1408 | // semantics of ARC truly do not do so. | |
1409 | if (IsNeverTail(Class)) { | |
1410 | Changed = true; | |
1a4d82fc | 1411 | DEBUG(dbgs() << "Removing tail keyword from function: " << *Inst << |
970d7e83 LB |
1412 | "\n"); |
1413 | cast<CallInst>(Inst)->setTailCall(false); | |
1414 | } | |
1415 | ||
1416 | // Set nounwind as needed. | |
1417 | if (IsNoThrow(Class)) { | |
1418 | Changed = true; | |
1a4d82fc JJ |
1419 | DEBUG(dbgs() << "Found no throw class. Setting nounwind on: " << *Inst |
1420 | << "\n"); | |
970d7e83 LB |
1421 | cast<CallInst>(Inst)->setDoesNotThrow(); |
1422 | } | |
1423 | ||
1424 | if (!IsNoopOnNull(Class)) { | |
1425 | UsedInThisFunction |= 1 << Class; | |
1426 | continue; | |
1427 | } | |
1428 | ||
1429 | const Value *Arg = GetObjCArg(Inst); | |
1430 | ||
1431 | // ARC calls with null are no-ops. Delete them. | |
1a4d82fc | 1432 | if (IsNullOrUndef(Arg)) { |
970d7e83 LB |
1433 | Changed = true; |
1434 | ++NumNoops; | |
1a4d82fc JJ |
1435 | DEBUG(dbgs() << "ARC calls with null are no-ops. Erasing: " << *Inst |
1436 | << "\n"); | |
970d7e83 LB |
1437 | EraseInstruction(Inst); |
1438 | continue; | |
1439 | } | |
1440 | ||
1441 | // Keep track of which of retain, release, autorelease, and retain_block | |
1442 | // are actually present in this function. | |
1443 | UsedInThisFunction |= 1 << Class; | |
1444 | ||
1445 | // If Arg is a PHI, and one or more incoming values to the | |
1446 | // PHI are null, and the call is control-equivalent to the PHI, and there | |
1447 | // are no relevant side effects between the PHI and the call, the call | |
1448 | // could be pushed up to just those paths with non-null incoming values. | |
1449 | // For now, don't bother splitting critical edges for this. | |
1450 | SmallVector<std::pair<Instruction *, const Value *>, 4> Worklist; | |
1451 | Worklist.push_back(std::make_pair(Inst, Arg)); | |
1452 | do { | |
1453 | std::pair<Instruction *, const Value *> Pair = Worklist.pop_back_val(); | |
1454 | Inst = Pair.first; | |
1455 | Arg = Pair.second; | |
1456 | ||
1457 | const PHINode *PN = dyn_cast<PHINode>(Arg); | |
1458 | if (!PN) continue; | |
1459 | ||
1460 | // Determine if the PHI has any null operands, or any incoming | |
1461 | // critical edges. | |
1462 | bool HasNull = false; | |
1463 | bool HasCriticalEdges = false; | |
1464 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { | |
1465 | Value *Incoming = | |
1466 | StripPointerCastsAndObjCCalls(PN->getIncomingValue(i)); | |
1a4d82fc | 1467 | if (IsNullOrUndef(Incoming)) |
970d7e83 LB |
1468 | HasNull = true; |
1469 | else if (cast<TerminatorInst>(PN->getIncomingBlock(i)->back()) | |
1470 | .getNumSuccessors() != 1) { | |
1471 | HasCriticalEdges = true; | |
1472 | break; | |
1473 | } | |
1474 | } | |
1475 | // If we have null operands and no critical edges, optimize. | |
1476 | if (!HasCriticalEdges && HasNull) { | |
1477 | SmallPtrSet<Instruction *, 4> DependingInstructions; | |
1478 | SmallPtrSet<const BasicBlock *, 4> Visited; | |
1479 | ||
1480 | // Check that there is nothing that cares about the reference | |
1481 | // count between the call and the phi. | |
1482 | switch (Class) { | |
1483 | case IC_Retain: | |
1484 | case IC_RetainBlock: | |
1485 | // These can always be moved up. | |
1486 | break; | |
1487 | case IC_Release: | |
1488 | // These can't be moved across things that care about the retain | |
1489 | // count. | |
1490 | FindDependencies(NeedsPositiveRetainCount, Arg, | |
1491 | Inst->getParent(), Inst, | |
1492 | DependingInstructions, Visited, PA); | |
1493 | break; | |
1494 | case IC_Autorelease: | |
1495 | // These can't be moved across autorelease pool scope boundaries. | |
1496 | FindDependencies(AutoreleasePoolBoundary, Arg, | |
1497 | Inst->getParent(), Inst, | |
1498 | DependingInstructions, Visited, PA); | |
1499 | break; | |
1500 | case IC_RetainRV: | |
1501 | case IC_AutoreleaseRV: | |
1502 | // Don't move these; the RV optimization depends on the autoreleaseRV | |
1503 | // being tail called, and the retainRV being immediately after a call | |
1504 | // (which might still happen if we get lucky with codegen layout, but | |
1505 | // it's not worth taking the chance). | |
1506 | continue; | |
1507 | default: | |
1508 | llvm_unreachable("Invalid dependence flavor"); | |
1509 | } | |
1510 | ||
1511 | if (DependingInstructions.size() == 1 && | |
1512 | *DependingInstructions.begin() == PN) { | |
1513 | Changed = true; | |
1514 | ++NumPartialNoops; | |
1515 | // Clone the call into each predecessor that has a non-null value. | |
1516 | CallInst *CInst = cast<CallInst>(Inst); | |
1517 | Type *ParamTy = CInst->getArgOperand(0)->getType(); | |
1518 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { | |
1519 | Value *Incoming = | |
1520 | StripPointerCastsAndObjCCalls(PN->getIncomingValue(i)); | |
1a4d82fc | 1521 | if (!IsNullOrUndef(Incoming)) { |
970d7e83 LB |
1522 | CallInst *Clone = cast<CallInst>(CInst->clone()); |
1523 | Value *Op = PN->getIncomingValue(i); | |
1524 | Instruction *InsertPos = &PN->getIncomingBlock(i)->back(); | |
1525 | if (Op->getType() != ParamTy) | |
1526 | Op = new BitCastInst(Op, ParamTy, "", InsertPos); | |
1527 | Clone->setArgOperand(0, Op); | |
1528 | Clone->insertBefore(InsertPos); | |
1529 | ||
1a4d82fc | 1530 | DEBUG(dbgs() << "Cloning " |
970d7e83 | 1531 | << *CInst << "\n" |
1a4d82fc | 1532 | "And inserting clone at " << *InsertPos << "\n"); |
970d7e83 LB |
1533 | Worklist.push_back(std::make_pair(Clone, Incoming)); |
1534 | } | |
1535 | } | |
1536 | // Erase the original call. | |
1537 | DEBUG(dbgs() << "Erasing: " << *CInst << "\n"); | |
1538 | EraseInstruction(CInst); | |
1539 | continue; | |
1540 | } | |
1541 | } | |
1542 | } while (!Worklist.empty()); | |
1543 | } | |
1a4d82fc JJ |
1544 | } |
1545 | ||
1546 | /// If we have a top down pointer in the S_Use state, make sure that there are | |
1547 | /// no CFG hazards by checking the states of various bottom up pointers. | |
1548 | static void CheckForUseCFGHazard(const Sequence SuccSSeq, | |
1549 | const bool SuccSRRIKnownSafe, | |
1550 | PtrState &S, | |
1551 | bool &SomeSuccHasSame, | |
1552 | bool &AllSuccsHaveSame, | |
1553 | bool &NotAllSeqEqualButKnownSafe, | |
1554 | bool &ShouldContinue) { | |
1555 | switch (SuccSSeq) { | |
1556 | case S_CanRelease: { | |
1557 | if (!S.IsKnownSafe() && !SuccSRRIKnownSafe) { | |
1558 | S.ClearSequenceProgress(); | |
1559 | break; | |
1560 | } | |
1561 | S.SetCFGHazardAfflicted(true); | |
1562 | ShouldContinue = true; | |
1563 | break; | |
1564 | } | |
1565 | case S_Use: | |
1566 | SomeSuccHasSame = true; | |
1567 | break; | |
1568 | case S_Stop: | |
1569 | case S_Release: | |
1570 | case S_MovableRelease: | |
1571 | if (!S.IsKnownSafe() && !SuccSRRIKnownSafe) | |
1572 | AllSuccsHaveSame = false; | |
1573 | else | |
1574 | NotAllSeqEqualButKnownSafe = true; | |
1575 | break; | |
1576 | case S_Retain: | |
1577 | llvm_unreachable("bottom-up pointer in retain state!"); | |
1578 | case S_None: | |
1579 | llvm_unreachable("This should have been handled earlier."); | |
1580 | } | |
1581 | } | |
1582 | ||
1583 | /// If we have a Top Down pointer in the S_CanRelease state, make sure that | |
1584 | /// there are no CFG hazards by checking the states of various bottom up | |
1585 | /// pointers. | |
1586 | static void CheckForCanReleaseCFGHazard(const Sequence SuccSSeq, | |
1587 | const bool SuccSRRIKnownSafe, | |
1588 | PtrState &S, | |
1589 | bool &SomeSuccHasSame, | |
1590 | bool &AllSuccsHaveSame, | |
1591 | bool &NotAllSeqEqualButKnownSafe) { | |
1592 | switch (SuccSSeq) { | |
1593 | case S_CanRelease: | |
1594 | SomeSuccHasSame = true; | |
1595 | break; | |
1596 | case S_Stop: | |
1597 | case S_Release: | |
1598 | case S_MovableRelease: | |
1599 | case S_Use: | |
1600 | if (!S.IsKnownSafe() && !SuccSRRIKnownSafe) | |
1601 | AllSuccsHaveSame = false; | |
1602 | else | |
1603 | NotAllSeqEqualButKnownSafe = true; | |
1604 | break; | |
1605 | case S_Retain: | |
1606 | llvm_unreachable("bottom-up pointer in retain state!"); | |
1607 | case S_None: | |
1608 | llvm_unreachable("This should have been handled earlier."); | |
1609 | } | |
970d7e83 LB |
1610 | } |
1611 | ||
1612 | /// Check for critical edges, loop boundaries, irreducible control flow, or | |
1613 | /// other CFG structures where moving code across the edge would result in it | |
1614 | /// being executed more. | |
1615 | void | |
1616 | ObjCARCOpt::CheckForCFGHazards(const BasicBlock *BB, | |
1617 | DenseMap<const BasicBlock *, BBState> &BBStates, | |
1618 | BBState &MyStates) const { | |
1619 | // If any top-down local-use or possible-dec has a succ which is earlier in | |
1620 | // the sequence, forget it. | |
1621 | for (BBState::ptr_iterator I = MyStates.top_down_ptr_begin(), | |
1a4d82fc JJ |
1622 | E = MyStates.top_down_ptr_end(); I != E; ++I) { |
1623 | PtrState &S = I->second; | |
1624 | const Sequence Seq = I->second.GetSeq(); | |
1625 | ||
1626 | // We only care about S_Retain, S_CanRelease, and S_Use. | |
1627 | if (Seq == S_None) | |
1628 | continue; | |
1629 | ||
1630 | // Make sure that if extra top down states are added in the future that this | |
1631 | // code is updated to handle it. | |
1632 | assert((Seq == S_Retain || Seq == S_CanRelease || Seq == S_Use) && | |
1633 | "Unknown top down sequence state."); | |
1634 | ||
1635 | const Value *Arg = I->first; | |
1636 | const TerminatorInst *TI = cast<TerminatorInst>(&BB->back()); | |
1637 | bool SomeSuccHasSame = false; | |
1638 | bool AllSuccsHaveSame = true; | |
1639 | bool NotAllSeqEqualButKnownSafe = false; | |
1640 | ||
1641 | succ_const_iterator SI(TI), SE(TI, false); | |
1642 | ||
1643 | for (; SI != SE; ++SI) { | |
1644 | // If VisitBottomUp has pointer information for this successor, take | |
1645 | // what we know about it. | |
1646 | const DenseMap<const BasicBlock *, BBState>::iterator BBI = | |
1647 | BBStates.find(*SI); | |
1648 | assert(BBI != BBStates.end()); | |
1649 | const PtrState &SuccS = BBI->second.getPtrBottomUpState(Arg); | |
1650 | const Sequence SuccSSeq = SuccS.GetSeq(); | |
1651 | ||
1652 | // If bottom up, the pointer is in an S_None state, clear the sequence | |
1653 | // progress since the sequence in the bottom up state finished | |
1654 | // suggesting a mismatch in between retains/releases. This is true for | |
1655 | // all three cases that we are handling here: S_Retain, S_Use, and | |
1656 | // S_CanRelease. | |
1657 | if (SuccSSeq == S_None) { | |
970d7e83 | 1658 | S.ClearSequenceProgress(); |
1a4d82fc JJ |
1659 | continue; |
1660 | } | |
1661 | ||
1662 | // If we have S_Use or S_CanRelease, perform our check for cfg hazard | |
1663 | // checks. | |
1664 | const bool SuccSRRIKnownSafe = SuccS.IsKnownSafe(); | |
1665 | ||
1666 | // *NOTE* We do not use Seq from above here since we are allowing for | |
1667 | // S.GetSeq() to change while we are visiting basic blocks. | |
1668 | switch(S.GetSeq()) { | |
1669 | case S_Use: { | |
1670 | bool ShouldContinue = false; | |
1671 | CheckForUseCFGHazard(SuccSSeq, SuccSRRIKnownSafe, S, SomeSuccHasSame, | |
1672 | AllSuccsHaveSame, NotAllSeqEqualButKnownSafe, | |
1673 | ShouldContinue); | |
1674 | if (ShouldContinue) | |
970d7e83 | 1675 | continue; |
1a4d82fc JJ |
1676 | break; |
1677 | } | |
1678 | case S_CanRelease: { | |
1679 | CheckForCanReleaseCFGHazard(SuccSSeq, SuccSRRIKnownSafe, S, | |
1680 | SomeSuccHasSame, AllSuccsHaveSame, | |
1681 | NotAllSeqEqualButKnownSafe); | |
1682 | break; | |
1683 | } | |
1684 | case S_Retain: | |
1685 | case S_None: | |
1686 | case S_Stop: | |
1687 | case S_Release: | |
1688 | case S_MovableRelease: | |
1689 | break; | |
970d7e83 | 1690 | } |
970d7e83 | 1691 | } |
1a4d82fc JJ |
1692 | |
1693 | // If the state at the other end of any of the successor edges | |
1694 | // matches the current state, require all edges to match. This | |
1695 | // guards against loops in the middle of a sequence. | |
1696 | if (SomeSuccHasSame && !AllSuccsHaveSame) { | |
1697 | S.ClearSequenceProgress(); | |
1698 | } else if (NotAllSeqEqualButKnownSafe) { | |
1699 | // If we would have cleared the state foregoing the fact that we are known | |
1700 | // safe, stop code motion. This is because whether or not it is safe to | |
1701 | // remove RR pairs via KnownSafe is an orthogonal concept to whether we | |
1702 | // are allowed to perform code motion. | |
1703 | S.SetCFGHazardAfflicted(true); | |
970d7e83 | 1704 | } |
1a4d82fc | 1705 | } |
970d7e83 LB |
1706 | } |
1707 | ||
1708 | bool | |
1709 | ObjCARCOpt::VisitInstructionBottomUp(Instruction *Inst, | |
1710 | BasicBlock *BB, | |
1711 | MapVector<Value *, RRInfo> &Retains, | |
1712 | BBState &MyStates) { | |
1713 | bool NestingDetected = false; | |
1714 | InstructionClass Class = GetInstructionClass(Inst); | |
1a4d82fc JJ |
1715 | const Value *Arg = nullptr; |
1716 | ||
1717 | DEBUG(dbgs() << "Class: " << Class << "\n"); | |
970d7e83 LB |
1718 | |
1719 | switch (Class) { | |
1720 | case IC_Release: { | |
1721 | Arg = GetObjCArg(Inst); | |
1722 | ||
1723 | PtrState &S = MyStates.getPtrBottomUpState(Arg); | |
1724 | ||
1725 | // If we see two releases in a row on the same pointer. If so, make | |
1726 | // a note, and we'll cicle back to revisit it after we've | |
1727 | // hopefully eliminated the second release, which may allow us to | |
1728 | // eliminate the first release too. | |
1729 | // Theoretically we could implement removal of nested retain+release | |
1730 | // pairs by making PtrState hold a stack of states, but this is | |
1731 | // simple and avoids adding overhead for the non-nested case. | |
1732 | if (S.GetSeq() == S_Release || S.GetSeq() == S_MovableRelease) { | |
1a4d82fc | 1733 | DEBUG(dbgs() << "Found nested releases (i.e. a release pair)\n"); |
970d7e83 LB |
1734 | NestingDetected = true; |
1735 | } | |
1736 | ||
1737 | MDNode *ReleaseMetadata = Inst->getMetadata(ImpreciseReleaseMDKind); | |
1a4d82fc JJ |
1738 | Sequence NewSeq = ReleaseMetadata ? S_MovableRelease : S_Release; |
1739 | ANNOTATE_BOTTOMUP(Inst, Arg, S.GetSeq(), NewSeq); | |
1740 | S.ResetSequenceProgress(NewSeq); | |
1741 | S.SetReleaseMetadata(ReleaseMetadata); | |
1742 | S.SetKnownSafe(S.HasKnownPositiveRefCount()); | |
1743 | S.SetTailCallRelease(cast<CallInst>(Inst)->isTailCall()); | |
1744 | S.InsertCall(Inst); | |
970d7e83 LB |
1745 | S.SetKnownPositiveRefCount(); |
1746 | break; | |
1747 | } | |
1748 | case IC_RetainBlock: | |
1a4d82fc JJ |
1749 | // In OptimizeIndividualCalls, we have strength reduced all optimizable |
1750 | // objc_retainBlocks to objc_retains. Thus at this point any | |
1751 | // objc_retainBlocks that we see are not optimizable. | |
1752 | break; | |
970d7e83 LB |
1753 | case IC_Retain: |
1754 | case IC_RetainRV: { | |
1755 | Arg = GetObjCArg(Inst); | |
1756 | ||
1757 | PtrState &S = MyStates.getPtrBottomUpState(Arg); | |
1758 | S.SetKnownPositiveRefCount(); | |
1759 | ||
1a4d82fc JJ |
1760 | Sequence OldSeq = S.GetSeq(); |
1761 | switch (OldSeq) { | |
970d7e83 LB |
1762 | case S_Stop: |
1763 | case S_Release: | |
1764 | case S_MovableRelease: | |
1765 | case S_Use: | |
1a4d82fc JJ |
1766 | // If OldSeq is not S_Use or OldSeq is S_Use and we are tracking an |
1767 | // imprecise release, clear our reverse insertion points. | |
1768 | if (OldSeq != S_Use || S.IsTrackingImpreciseReleases()) | |
1769 | S.ClearReverseInsertPts(); | |
970d7e83 LB |
1770 | // FALL THROUGH |
1771 | case S_CanRelease: | |
1772 | // Don't do retain+release tracking for IC_RetainRV, because it's | |
1773 | // better to let it remain as the first instruction after a call. | |
1a4d82fc JJ |
1774 | if (Class != IC_RetainRV) |
1775 | Retains[Inst] = S.GetRRInfo(); | |
970d7e83 LB |
1776 | S.ClearSequenceProgress(); |
1777 | break; | |
1778 | case S_None: | |
1779 | break; | |
1780 | case S_Retain: | |
1781 | llvm_unreachable("bottom-up pointer in retain state!"); | |
1782 | } | |
1a4d82fc JJ |
1783 | ANNOTATE_BOTTOMUP(Inst, Arg, OldSeq, S.GetSeq()); |
1784 | // A retain moving bottom up can be a use. | |
1785 | break; | |
970d7e83 LB |
1786 | } |
1787 | case IC_AutoreleasepoolPop: | |
1788 | // Conservatively, clear MyStates for all known pointers. | |
1789 | MyStates.clearBottomUpPointers(); | |
1790 | return NestingDetected; | |
1791 | case IC_AutoreleasepoolPush: | |
1792 | case IC_None: | |
1793 | // These are irrelevant. | |
1794 | return NestingDetected; | |
1a4d82fc JJ |
1795 | case IC_User: |
1796 | // If we have a store into an alloca of a pointer we are tracking, the | |
1797 | // pointer has multiple owners implying that we must be more conservative. | |
1798 | // | |
1799 | // This comes up in the context of a pointer being ``KnownSafe''. In the | |
1800 | // presence of a block being initialized, the frontend will emit the | |
1801 | // objc_retain on the original pointer and the release on the pointer loaded | |
1802 | // from the alloca. The optimizer will through the provenance analysis | |
1803 | // realize that the two are related, but since we only require KnownSafe in | |
1804 | // one direction, will match the inner retain on the original pointer with | |
1805 | // the guard release on the original pointer. This is fixed by ensuring that | |
1806 | // in the presence of allocas we only unconditionally remove pointers if | |
1807 | // both our retain and our release are KnownSafe. | |
1808 | if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) { | |
1809 | if (AreAnyUnderlyingObjectsAnAlloca(SI->getPointerOperand())) { | |
1810 | BBState::ptr_iterator I = MyStates.findPtrBottomUpState( | |
1811 | StripPointerCastsAndObjCCalls(SI->getValueOperand())); | |
1812 | if (I != MyStates.bottom_up_ptr_end()) | |
1813 | MultiOwnersSet.insert(I->first); | |
1814 | } | |
1815 | } | |
1816 | break; | |
970d7e83 LB |
1817 | default: |
1818 | break; | |
1819 | } | |
1820 | ||
1821 | // Consider any other possible effects of this instruction on each | |
1822 | // pointer being tracked. | |
1823 | for (BBState::ptr_iterator MI = MyStates.bottom_up_ptr_begin(), | |
1824 | ME = MyStates.bottom_up_ptr_end(); MI != ME; ++MI) { | |
1825 | const Value *Ptr = MI->first; | |
1826 | if (Ptr == Arg) | |
1827 | continue; // Handled above. | |
1828 | PtrState &S = MI->second; | |
1829 | Sequence Seq = S.GetSeq(); | |
1830 | ||
1831 | // Check for possible releases. | |
1832 | if (CanAlterRefCount(Inst, Ptr, PA, Class)) { | |
1a4d82fc JJ |
1833 | DEBUG(dbgs() << "CanAlterRefCount: Seq: " << Seq << "; " << *Ptr |
1834 | << "\n"); | |
1835 | S.ClearKnownPositiveRefCount(); | |
970d7e83 LB |
1836 | switch (Seq) { |
1837 | case S_Use: | |
1838 | S.SetSeq(S_CanRelease); | |
1a4d82fc | 1839 | ANNOTATE_BOTTOMUP(Inst, Ptr, Seq, S.GetSeq()); |
970d7e83 LB |
1840 | continue; |
1841 | case S_CanRelease: | |
1842 | case S_Release: | |
1843 | case S_MovableRelease: | |
1844 | case S_Stop: | |
1845 | case S_None: | |
1846 | break; | |
1847 | case S_Retain: | |
1848 | llvm_unreachable("bottom-up pointer in retain state!"); | |
1849 | } | |
1850 | } | |
1851 | ||
1852 | // Check for possible direct uses. | |
1853 | switch (Seq) { | |
1854 | case S_Release: | |
1855 | case S_MovableRelease: | |
1856 | if (CanUse(Inst, Ptr, PA, Class)) { | |
1a4d82fc JJ |
1857 | DEBUG(dbgs() << "CanUse: Seq: " << Seq << "; " << *Ptr |
1858 | << "\n"); | |
1859 | assert(!S.HasReverseInsertPts()); | |
970d7e83 LB |
1860 | // If this is an invoke instruction, we're scanning it as part of |
1861 | // one of its successor blocks, since we can't insert code after it | |
1862 | // in its own block, and we don't want to split critical edges. | |
1863 | if (isa<InvokeInst>(Inst)) | |
1a4d82fc | 1864 | S.InsertReverseInsertPt(BB->getFirstInsertionPt()); |
970d7e83 | 1865 | else |
1a4d82fc | 1866 | S.InsertReverseInsertPt(std::next(BasicBlock::iterator(Inst))); |
970d7e83 | 1867 | S.SetSeq(S_Use); |
1a4d82fc JJ |
1868 | ANNOTATE_BOTTOMUP(Inst, Ptr, Seq, S_Use); |
1869 | } else if (Seq == S_Release && IsUser(Class)) { | |
1870 | DEBUG(dbgs() << "PreciseReleaseUse: Seq: " << Seq << "; " << *Ptr | |
1871 | << "\n"); | |
970d7e83 LB |
1872 | // Non-movable releases depend on any possible objc pointer use. |
1873 | S.SetSeq(S_Stop); | |
1a4d82fc JJ |
1874 | ANNOTATE_BOTTOMUP(Inst, Ptr, S_Release, S_Stop); |
1875 | assert(!S.HasReverseInsertPts()); | |
970d7e83 LB |
1876 | // As above; handle invoke specially. |
1877 | if (isa<InvokeInst>(Inst)) | |
1a4d82fc | 1878 | S.InsertReverseInsertPt(BB->getFirstInsertionPt()); |
970d7e83 | 1879 | else |
1a4d82fc | 1880 | S.InsertReverseInsertPt(std::next(BasicBlock::iterator(Inst))); |
970d7e83 LB |
1881 | } |
1882 | break; | |
1883 | case S_Stop: | |
1a4d82fc JJ |
1884 | if (CanUse(Inst, Ptr, PA, Class)) { |
1885 | DEBUG(dbgs() << "PreciseStopUse: Seq: " << Seq << "; " << *Ptr | |
1886 | << "\n"); | |
970d7e83 | 1887 | S.SetSeq(S_Use); |
1a4d82fc JJ |
1888 | ANNOTATE_BOTTOMUP(Inst, Ptr, Seq, S_Use); |
1889 | } | |
970d7e83 LB |
1890 | break; |
1891 | case S_CanRelease: | |
1892 | case S_Use: | |
1893 | case S_None: | |
1894 | break; | |
1895 | case S_Retain: | |
1896 | llvm_unreachable("bottom-up pointer in retain state!"); | |
1897 | } | |
1898 | } | |
1899 | ||
1900 | return NestingDetected; | |
1901 | } | |
1902 | ||
1903 | bool | |
1904 | ObjCARCOpt::VisitBottomUp(BasicBlock *BB, | |
1905 | DenseMap<const BasicBlock *, BBState> &BBStates, | |
1906 | MapVector<Value *, RRInfo> &Retains) { | |
1a4d82fc JJ |
1907 | |
1908 | DEBUG(dbgs() << "\n== ObjCARCOpt::VisitBottomUp ==\n"); | |
1909 | ||
970d7e83 LB |
1910 | bool NestingDetected = false; |
1911 | BBState &MyStates = BBStates[BB]; | |
1912 | ||
1913 | // Merge the states from each successor to compute the initial state | |
1914 | // for the current block. | |
1915 | BBState::edge_iterator SI(MyStates.succ_begin()), | |
1916 | SE(MyStates.succ_end()); | |
1917 | if (SI != SE) { | |
1918 | const BasicBlock *Succ = *SI; | |
1919 | DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Succ); | |
1920 | assert(I != BBStates.end()); | |
1921 | MyStates.InitFromSucc(I->second); | |
1922 | ++SI; | |
1923 | for (; SI != SE; ++SI) { | |
1924 | Succ = *SI; | |
1925 | I = BBStates.find(Succ); | |
1926 | assert(I != BBStates.end()); | |
1927 | MyStates.MergeSucc(I->second); | |
1928 | } | |
1929 | } | |
1930 | ||
1a4d82fc JJ |
1931 | // If ARC Annotations are enabled, output the current state of pointers at the |
1932 | // bottom of the basic block. | |
1933 | ANNOTATE_BOTTOMUP_BBEND(MyStates, BB); | |
1934 | ||
970d7e83 LB |
1935 | // Visit all the instructions, bottom-up. |
1936 | for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; --I) { | |
1a4d82fc | 1937 | Instruction *Inst = std::prev(I); |
970d7e83 LB |
1938 | |
1939 | // Invoke instructions are visited as part of their successors (below). | |
1940 | if (isa<InvokeInst>(Inst)) | |
1941 | continue; | |
1942 | ||
1a4d82fc | 1943 | DEBUG(dbgs() << "Visiting " << *Inst << "\n"); |
970d7e83 LB |
1944 | |
1945 | NestingDetected |= VisitInstructionBottomUp(Inst, BB, Retains, MyStates); | |
1946 | } | |
1947 | ||
1948 | // If there's a predecessor with an invoke, visit the invoke as if it were | |
1949 | // part of this block, since we can't insert code after an invoke in its own | |
1950 | // block, and we don't want to split critical edges. | |
1951 | for (BBState::edge_iterator PI(MyStates.pred_begin()), | |
1952 | PE(MyStates.pred_end()); PI != PE; ++PI) { | |
1953 | BasicBlock *Pred = *PI; | |
1954 | if (InvokeInst *II = dyn_cast<InvokeInst>(&Pred->back())) | |
1955 | NestingDetected |= VisitInstructionBottomUp(II, BB, Retains, MyStates); | |
1956 | } | |
1957 | ||
1a4d82fc JJ |
1958 | // If ARC Annotations are enabled, output the current state of pointers at the |
1959 | // top of the basic block. | |
1960 | ANNOTATE_BOTTOMUP_BBSTART(MyStates, BB); | |
1961 | ||
970d7e83 LB |
1962 | return NestingDetected; |
1963 | } | |
1964 | ||
1965 | bool | |
1966 | ObjCARCOpt::VisitInstructionTopDown(Instruction *Inst, | |
1967 | DenseMap<Value *, RRInfo> &Releases, | |
1968 | BBState &MyStates) { | |
1969 | bool NestingDetected = false; | |
1970 | InstructionClass Class = GetInstructionClass(Inst); | |
1a4d82fc | 1971 | const Value *Arg = nullptr; |
970d7e83 LB |
1972 | |
1973 | switch (Class) { | |
1974 | case IC_RetainBlock: | |
1a4d82fc JJ |
1975 | // In OptimizeIndividualCalls, we have strength reduced all optimizable |
1976 | // objc_retainBlocks to objc_retains. Thus at this point any | |
1977 | // objc_retainBlocks that we see are not optimizable. | |
1978 | break; | |
970d7e83 LB |
1979 | case IC_Retain: |
1980 | case IC_RetainRV: { | |
1981 | Arg = GetObjCArg(Inst); | |
1982 | ||
1983 | PtrState &S = MyStates.getPtrTopDownState(Arg); | |
1984 | ||
1985 | // Don't do retain+release tracking for IC_RetainRV, because it's | |
1986 | // better to let it remain as the first instruction after a call. | |
1987 | if (Class != IC_RetainRV) { | |
1988 | // If we see two retains in a row on the same pointer. If so, make | |
1989 | // a note, and we'll cicle back to revisit it after we've | |
1990 | // hopefully eliminated the second retain, which may allow us to | |
1991 | // eliminate the first retain too. | |
1992 | // Theoretically we could implement removal of nested retain+release | |
1993 | // pairs by making PtrState hold a stack of states, but this is | |
1994 | // simple and avoids adding overhead for the non-nested case. | |
1995 | if (S.GetSeq() == S_Retain) | |
1996 | NestingDetected = true; | |
1997 | ||
1a4d82fc | 1998 | ANNOTATE_TOPDOWN(Inst, Arg, S.GetSeq(), S_Retain); |
970d7e83 | 1999 | S.ResetSequenceProgress(S_Retain); |
1a4d82fc JJ |
2000 | S.SetKnownSafe(S.HasKnownPositiveRefCount()); |
2001 | S.InsertCall(Inst); | |
970d7e83 LB |
2002 | } |
2003 | ||
2004 | S.SetKnownPositiveRefCount(); | |
2005 | ||
2006 | // A retain can be a potential use; procede to the generic checking | |
2007 | // code below. | |
2008 | break; | |
2009 | } | |
2010 | case IC_Release: { | |
2011 | Arg = GetObjCArg(Inst); | |
2012 | ||
2013 | PtrState &S = MyStates.getPtrTopDownState(Arg); | |
1a4d82fc | 2014 | S.ClearKnownPositiveRefCount(); |
970d7e83 | 2015 | |
1a4d82fc JJ |
2016 | Sequence OldSeq = S.GetSeq(); |
2017 | ||
2018 | MDNode *ReleaseMetadata = Inst->getMetadata(ImpreciseReleaseMDKind); | |
2019 | ||
2020 | switch (OldSeq) { | |
970d7e83 LB |
2021 | case S_Retain: |
2022 | case S_CanRelease: | |
1a4d82fc JJ |
2023 | if (OldSeq == S_Retain || ReleaseMetadata != nullptr) |
2024 | S.ClearReverseInsertPts(); | |
970d7e83 LB |
2025 | // FALL THROUGH |
2026 | case S_Use: | |
1a4d82fc JJ |
2027 | S.SetReleaseMetadata(ReleaseMetadata); |
2028 | S.SetTailCallRelease(cast<CallInst>(Inst)->isTailCall()); | |
2029 | Releases[Inst] = S.GetRRInfo(); | |
2030 | ANNOTATE_TOPDOWN(Inst, Arg, S.GetSeq(), S_None); | |
970d7e83 LB |
2031 | S.ClearSequenceProgress(); |
2032 | break; | |
2033 | case S_None: | |
2034 | break; | |
2035 | case S_Stop: | |
2036 | case S_Release: | |
2037 | case S_MovableRelease: | |
2038 | llvm_unreachable("top-down pointer in release state!"); | |
2039 | } | |
2040 | break; | |
2041 | } | |
2042 | case IC_AutoreleasepoolPop: | |
2043 | // Conservatively, clear MyStates for all known pointers. | |
2044 | MyStates.clearTopDownPointers(); | |
2045 | return NestingDetected; | |
2046 | case IC_AutoreleasepoolPush: | |
2047 | case IC_None: | |
2048 | // These are irrelevant. | |
2049 | return NestingDetected; | |
2050 | default: | |
2051 | break; | |
2052 | } | |
2053 | ||
2054 | // Consider any other possible effects of this instruction on each | |
2055 | // pointer being tracked. | |
2056 | for (BBState::ptr_iterator MI = MyStates.top_down_ptr_begin(), | |
2057 | ME = MyStates.top_down_ptr_end(); MI != ME; ++MI) { | |
2058 | const Value *Ptr = MI->first; | |
2059 | if (Ptr == Arg) | |
2060 | continue; // Handled above. | |
2061 | PtrState &S = MI->second; | |
2062 | Sequence Seq = S.GetSeq(); | |
2063 | ||
2064 | // Check for possible releases. | |
2065 | if (CanAlterRefCount(Inst, Ptr, PA, Class)) { | |
1a4d82fc JJ |
2066 | DEBUG(dbgs() << "CanAlterRefCount: Seq: " << Seq << "; " << *Ptr |
2067 | << "\n"); | |
2068 | S.ClearKnownPositiveRefCount(); | |
970d7e83 LB |
2069 | switch (Seq) { |
2070 | case S_Retain: | |
2071 | S.SetSeq(S_CanRelease); | |
1a4d82fc JJ |
2072 | ANNOTATE_TOPDOWN(Inst, Ptr, Seq, S_CanRelease); |
2073 | assert(!S.HasReverseInsertPts()); | |
2074 | S.InsertReverseInsertPt(Inst); | |
970d7e83 LB |
2075 | |
2076 | // One call can't cause a transition from S_Retain to S_CanRelease | |
2077 | // and S_CanRelease to S_Use. If we've made the first transition, | |
2078 | // we're done. | |
2079 | continue; | |
2080 | case S_Use: | |
2081 | case S_CanRelease: | |
2082 | case S_None: | |
2083 | break; | |
2084 | case S_Stop: | |
2085 | case S_Release: | |
2086 | case S_MovableRelease: | |
2087 | llvm_unreachable("top-down pointer in release state!"); | |
2088 | } | |
2089 | } | |
2090 | ||
2091 | // Check for possible direct uses. | |
2092 | switch (Seq) { | |
2093 | case S_CanRelease: | |
1a4d82fc JJ |
2094 | if (CanUse(Inst, Ptr, PA, Class)) { |
2095 | DEBUG(dbgs() << "CanUse: Seq: " << Seq << "; " << *Ptr | |
2096 | << "\n"); | |
970d7e83 | 2097 | S.SetSeq(S_Use); |
1a4d82fc JJ |
2098 | ANNOTATE_TOPDOWN(Inst, Ptr, Seq, S_Use); |
2099 | } | |
970d7e83 LB |
2100 | break; |
2101 | case S_Retain: | |
2102 | case S_Use: | |
2103 | case S_None: | |
2104 | break; | |
2105 | case S_Stop: | |
2106 | case S_Release: | |
2107 | case S_MovableRelease: | |
2108 | llvm_unreachable("top-down pointer in release state!"); | |
2109 | } | |
2110 | } | |
2111 | ||
2112 | return NestingDetected; | |
2113 | } | |
2114 | ||
2115 | bool | |
2116 | ObjCARCOpt::VisitTopDown(BasicBlock *BB, | |
2117 | DenseMap<const BasicBlock *, BBState> &BBStates, | |
2118 | DenseMap<Value *, RRInfo> &Releases) { | |
1a4d82fc | 2119 | DEBUG(dbgs() << "\n== ObjCARCOpt::VisitTopDown ==\n"); |
970d7e83 LB |
2120 | bool NestingDetected = false; |
2121 | BBState &MyStates = BBStates[BB]; | |
2122 | ||
2123 | // Merge the states from each predecessor to compute the initial state | |
2124 | // for the current block. | |
2125 | BBState::edge_iterator PI(MyStates.pred_begin()), | |
2126 | PE(MyStates.pred_end()); | |
2127 | if (PI != PE) { | |
2128 | const BasicBlock *Pred = *PI; | |
2129 | DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Pred); | |
2130 | assert(I != BBStates.end()); | |
2131 | MyStates.InitFromPred(I->second); | |
2132 | ++PI; | |
2133 | for (; PI != PE; ++PI) { | |
2134 | Pred = *PI; | |
2135 | I = BBStates.find(Pred); | |
2136 | assert(I != BBStates.end()); | |
2137 | MyStates.MergePred(I->second); | |
2138 | } | |
2139 | } | |
2140 | ||
1a4d82fc JJ |
2141 | // If ARC Annotations are enabled, output the current state of pointers at the |
2142 | // top of the basic block. | |
2143 | ANNOTATE_TOPDOWN_BBSTART(MyStates, BB); | |
2144 | ||
970d7e83 LB |
2145 | // Visit all the instructions, top-down. |
2146 | for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { | |
2147 | Instruction *Inst = I; | |
2148 | ||
1a4d82fc | 2149 | DEBUG(dbgs() << "Visiting " << *Inst << "\n"); |
970d7e83 LB |
2150 | |
2151 | NestingDetected |= VisitInstructionTopDown(Inst, Releases, MyStates); | |
2152 | } | |
2153 | ||
1a4d82fc JJ |
2154 | // If ARC Annotations are enabled, output the current state of pointers at the |
2155 | // bottom of the basic block. | |
2156 | ANNOTATE_TOPDOWN_BBEND(MyStates, BB); | |
2157 | ||
2158 | #ifdef ARC_ANNOTATIONS | |
2159 | if (!(EnableARCAnnotations && DisableCheckForCFGHazards)) | |
2160 | #endif | |
970d7e83 LB |
2161 | CheckForCFGHazards(BB, BBStates, MyStates); |
2162 | return NestingDetected; | |
2163 | } | |
2164 | ||
2165 | static void | |
2166 | ComputePostOrders(Function &F, | |
2167 | SmallVectorImpl<BasicBlock *> &PostOrder, | |
2168 | SmallVectorImpl<BasicBlock *> &ReverseCFGPostOrder, | |
2169 | unsigned NoObjCARCExceptionsMDKind, | |
2170 | DenseMap<const BasicBlock *, BBState> &BBStates) { | |
2171 | /// The visited set, for doing DFS walks. | |
2172 | SmallPtrSet<BasicBlock *, 16> Visited; | |
2173 | ||
2174 | // Do DFS, computing the PostOrder. | |
2175 | SmallPtrSet<BasicBlock *, 16> OnStack; | |
2176 | SmallVector<std::pair<BasicBlock *, succ_iterator>, 16> SuccStack; | |
2177 | ||
2178 | // Functions always have exactly one entry block, and we don't have | |
2179 | // any other block that we treat like an entry block. | |
2180 | BasicBlock *EntryBB = &F.getEntryBlock(); | |
2181 | BBState &MyStates = BBStates[EntryBB]; | |
2182 | MyStates.SetAsEntry(); | |
2183 | TerminatorInst *EntryTI = cast<TerminatorInst>(&EntryBB->back()); | |
2184 | SuccStack.push_back(std::make_pair(EntryBB, succ_iterator(EntryTI))); | |
2185 | Visited.insert(EntryBB); | |
2186 | OnStack.insert(EntryBB); | |
2187 | do { | |
2188 | dfs_next_succ: | |
2189 | BasicBlock *CurrBB = SuccStack.back().first; | |
2190 | TerminatorInst *TI = cast<TerminatorInst>(&CurrBB->back()); | |
2191 | succ_iterator SE(TI, false); | |
2192 | ||
2193 | while (SuccStack.back().second != SE) { | |
2194 | BasicBlock *SuccBB = *SuccStack.back().second++; | |
85aaf69f | 2195 | if (Visited.insert(SuccBB).second) { |
970d7e83 LB |
2196 | TerminatorInst *TI = cast<TerminatorInst>(&SuccBB->back()); |
2197 | SuccStack.push_back(std::make_pair(SuccBB, succ_iterator(TI))); | |
2198 | BBStates[CurrBB].addSucc(SuccBB); | |
2199 | BBState &SuccStates = BBStates[SuccBB]; | |
2200 | SuccStates.addPred(CurrBB); | |
2201 | OnStack.insert(SuccBB); | |
2202 | goto dfs_next_succ; | |
2203 | } | |
2204 | ||
2205 | if (!OnStack.count(SuccBB)) { | |
2206 | BBStates[CurrBB].addSucc(SuccBB); | |
2207 | BBStates[SuccBB].addPred(CurrBB); | |
2208 | } | |
2209 | } | |
2210 | OnStack.erase(CurrBB); | |
2211 | PostOrder.push_back(CurrBB); | |
2212 | SuccStack.pop_back(); | |
2213 | } while (!SuccStack.empty()); | |
2214 | ||
2215 | Visited.clear(); | |
2216 | ||
2217 | // Do reverse-CFG DFS, computing the reverse-CFG PostOrder. | |
2218 | // Functions may have many exits, and there also blocks which we treat | |
2219 | // as exits due to ignored edges. | |
2220 | SmallVector<std::pair<BasicBlock *, BBState::edge_iterator>, 16> PredStack; | |
2221 | for (Function::iterator I = F.begin(), E = F.end(); I != E; ++I) { | |
2222 | BasicBlock *ExitBB = I; | |
2223 | BBState &MyStates = BBStates[ExitBB]; | |
2224 | if (!MyStates.isExit()) | |
2225 | continue; | |
2226 | ||
2227 | MyStates.SetAsExit(); | |
2228 | ||
2229 | PredStack.push_back(std::make_pair(ExitBB, MyStates.pred_begin())); | |
2230 | Visited.insert(ExitBB); | |
2231 | while (!PredStack.empty()) { | |
2232 | reverse_dfs_next_succ: | |
2233 | BBState::edge_iterator PE = BBStates[PredStack.back().first].pred_end(); | |
2234 | while (PredStack.back().second != PE) { | |
2235 | BasicBlock *BB = *PredStack.back().second++; | |
85aaf69f | 2236 | if (Visited.insert(BB).second) { |
970d7e83 LB |
2237 | PredStack.push_back(std::make_pair(BB, BBStates[BB].pred_begin())); |
2238 | goto reverse_dfs_next_succ; | |
2239 | } | |
2240 | } | |
2241 | ReverseCFGPostOrder.push_back(PredStack.pop_back_val().first); | |
2242 | } | |
2243 | } | |
2244 | } | |
2245 | ||
2246 | // Visit the function both top-down and bottom-up. | |
2247 | bool | |
2248 | ObjCARCOpt::Visit(Function &F, | |
2249 | DenseMap<const BasicBlock *, BBState> &BBStates, | |
2250 | MapVector<Value *, RRInfo> &Retains, | |
2251 | DenseMap<Value *, RRInfo> &Releases) { | |
2252 | ||
2253 | // Use reverse-postorder traversals, because we magically know that loops | |
2254 | // will be well behaved, i.e. they won't repeatedly call retain on a single | |
2255 | // pointer without doing a release. We can't use the ReversePostOrderTraversal | |
2256 | // class here because we want the reverse-CFG postorder to consider each | |
2257 | // function exit point, and we want to ignore selected cycle edges. | |
2258 | SmallVector<BasicBlock *, 16> PostOrder; | |
2259 | SmallVector<BasicBlock *, 16> ReverseCFGPostOrder; | |
2260 | ComputePostOrders(F, PostOrder, ReverseCFGPostOrder, | |
2261 | NoObjCARCExceptionsMDKind, | |
2262 | BBStates); | |
2263 | ||
2264 | // Use reverse-postorder on the reverse CFG for bottom-up. | |
2265 | bool BottomUpNestingDetected = false; | |
2266 | for (SmallVectorImpl<BasicBlock *>::const_reverse_iterator I = | |
2267 | ReverseCFGPostOrder.rbegin(), E = ReverseCFGPostOrder.rend(); | |
2268 | I != E; ++I) | |
2269 | BottomUpNestingDetected |= VisitBottomUp(*I, BBStates, Retains); | |
2270 | ||
2271 | // Use reverse-postorder for top-down. | |
2272 | bool TopDownNestingDetected = false; | |
2273 | for (SmallVectorImpl<BasicBlock *>::const_reverse_iterator I = | |
2274 | PostOrder.rbegin(), E = PostOrder.rend(); | |
2275 | I != E; ++I) | |
2276 | TopDownNestingDetected |= VisitTopDown(*I, BBStates, Releases); | |
2277 | ||
2278 | return TopDownNestingDetected && BottomUpNestingDetected; | |
2279 | } | |
2280 | ||
2281 | /// Move the calls in RetainsToMove and ReleasesToMove. | |
2282 | void ObjCARCOpt::MoveCalls(Value *Arg, | |
2283 | RRInfo &RetainsToMove, | |
2284 | RRInfo &ReleasesToMove, | |
2285 | MapVector<Value *, RRInfo> &Retains, | |
2286 | DenseMap<Value *, RRInfo> &Releases, | |
2287 | SmallVectorImpl<Instruction *> &DeadInsts, | |
2288 | Module *M) { | |
2289 | Type *ArgTy = Arg->getType(); | |
2290 | Type *ParamTy = PointerType::getUnqual(Type::getInt8Ty(ArgTy->getContext())); | |
2291 | ||
1a4d82fc JJ |
2292 | DEBUG(dbgs() << "== ObjCARCOpt::MoveCalls ==\n"); |
2293 | ||
970d7e83 | 2294 | // Insert the new retain and release calls. |
1a4d82fc | 2295 | for (Instruction *InsertPt : ReleasesToMove.ReverseInsertPts) { |
970d7e83 LB |
2296 | Value *MyArg = ArgTy == ParamTy ? Arg : |
2297 | new BitCastInst(Arg, ParamTy, "", InsertPt); | |
1a4d82fc JJ |
2298 | Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_Retain); |
2299 | CallInst *Call = CallInst::Create(Decl, MyArg, "", InsertPt); | |
970d7e83 | 2300 | Call->setDoesNotThrow(); |
1a4d82fc | 2301 | Call->setTailCall(); |
970d7e83 | 2302 | |
1a4d82fc JJ |
2303 | DEBUG(dbgs() << "Inserting new Retain: " << *Call << "\n" |
2304 | "At insertion point: " << *InsertPt << "\n"); | |
970d7e83 | 2305 | } |
1a4d82fc | 2306 | for (Instruction *InsertPt : RetainsToMove.ReverseInsertPts) { |
970d7e83 LB |
2307 | Value *MyArg = ArgTy == ParamTy ? Arg : |
2308 | new BitCastInst(Arg, ParamTy, "", InsertPt); | |
1a4d82fc JJ |
2309 | Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_Release); |
2310 | CallInst *Call = CallInst::Create(Decl, MyArg, "", InsertPt); | |
970d7e83 LB |
2311 | // Attach a clang.imprecise_release metadata tag, if appropriate. |
2312 | if (MDNode *M = ReleasesToMove.ReleaseMetadata) | |
2313 | Call->setMetadata(ImpreciseReleaseMDKind, M); | |
2314 | Call->setDoesNotThrow(); | |
2315 | if (ReleasesToMove.IsTailCallRelease) | |
2316 | Call->setTailCall(); | |
2317 | ||
1a4d82fc JJ |
2318 | DEBUG(dbgs() << "Inserting new Release: " << *Call << "\n" |
2319 | "At insertion point: " << *InsertPt << "\n"); | |
970d7e83 LB |
2320 | } |
2321 | ||
2322 | // Delete the original retain and release calls. | |
1a4d82fc | 2323 | for (Instruction *OrigRetain : RetainsToMove.Calls) { |
970d7e83 LB |
2324 | Retains.blot(OrigRetain); |
2325 | DeadInsts.push_back(OrigRetain); | |
1a4d82fc | 2326 | DEBUG(dbgs() << "Deleting retain: " << *OrigRetain << "\n"); |
970d7e83 | 2327 | } |
1a4d82fc | 2328 | for (Instruction *OrigRelease : ReleasesToMove.Calls) { |
970d7e83 LB |
2329 | Releases.erase(OrigRelease); |
2330 | DeadInsts.push_back(OrigRelease); | |
1a4d82fc | 2331 | DEBUG(dbgs() << "Deleting release: " << *OrigRelease << "\n"); |
970d7e83 | 2332 | } |
1a4d82fc | 2333 | |
970d7e83 LB |
2334 | } |
2335 | ||
2336 | bool | |
2337 | ObjCARCOpt::ConnectTDBUTraversals(DenseMap<const BasicBlock *, BBState> | |
2338 | &BBStates, | |
2339 | MapVector<Value *, RRInfo> &Retains, | |
2340 | DenseMap<Value *, RRInfo> &Releases, | |
2341 | Module *M, | |
1a4d82fc JJ |
2342 | SmallVectorImpl<Instruction *> &NewRetains, |
2343 | SmallVectorImpl<Instruction *> &NewReleases, | |
2344 | SmallVectorImpl<Instruction *> &DeadInsts, | |
970d7e83 LB |
2345 | RRInfo &RetainsToMove, |
2346 | RRInfo &ReleasesToMove, | |
2347 | Value *Arg, | |
2348 | bool KnownSafe, | |
2349 | bool &AnyPairsCompletelyEliminated) { | |
2350 | // If a pair happens in a region where it is known that the reference count | |
1a4d82fc JJ |
2351 | // is already incremented, we can similarly ignore possible decrements unless |
2352 | // we are dealing with a retainable object with multiple provenance sources. | |
970d7e83 | 2353 | bool KnownSafeTD = true, KnownSafeBU = true; |
1a4d82fc JJ |
2354 | bool MultipleOwners = false; |
2355 | bool CFGHazardAfflicted = false; | |
970d7e83 LB |
2356 | |
2357 | // Connect the dots between the top-down-collected RetainsToMove and | |
2358 | // bottom-up-collected ReleasesToMove to form sets of related calls. | |
2359 | // This is an iterative process so that we connect multiple releases | |
2360 | // to multiple retains if needed. | |
2361 | unsigned OldDelta = 0; | |
2362 | unsigned NewDelta = 0; | |
2363 | unsigned OldCount = 0; | |
2364 | unsigned NewCount = 0; | |
2365 | bool FirstRelease = true; | |
970d7e83 LB |
2366 | for (;;) { |
2367 | for (SmallVectorImpl<Instruction *>::const_iterator | |
2368 | NI = NewRetains.begin(), NE = NewRetains.end(); NI != NE; ++NI) { | |
2369 | Instruction *NewRetain = *NI; | |
2370 | MapVector<Value *, RRInfo>::const_iterator It = Retains.find(NewRetain); | |
2371 | assert(It != Retains.end()); | |
2372 | const RRInfo &NewRetainRRI = It->second; | |
2373 | KnownSafeTD &= NewRetainRRI.KnownSafe; | |
1a4d82fc JJ |
2374 | MultipleOwners = |
2375 | MultipleOwners || MultiOwnersSet.count(GetObjCArg(NewRetain)); | |
2376 | for (Instruction *NewRetainRelease : NewRetainRRI.Calls) { | |
970d7e83 LB |
2377 | DenseMap<Value *, RRInfo>::const_iterator Jt = |
2378 | Releases.find(NewRetainRelease); | |
2379 | if (Jt == Releases.end()) | |
2380 | return false; | |
2381 | const RRInfo &NewRetainReleaseRRI = Jt->second; | |
1a4d82fc JJ |
2382 | |
2383 | // If the release does not have a reference to the retain as well, | |
2384 | // something happened which is unaccounted for. Do not do anything. | |
2385 | // | |
2386 | // This can happen if we catch an additive overflow during path count | |
2387 | // merging. | |
2388 | if (!NewRetainReleaseRRI.Calls.count(NewRetain)) | |
2389 | return false; | |
2390 | ||
85aaf69f | 2391 | if (ReleasesToMove.Calls.insert(NewRetainRelease).second) { |
1a4d82fc JJ |
2392 | |
2393 | // If we overflow when we compute the path count, don't remove/move | |
2394 | // anything. | |
2395 | const BBState &NRRBBState = BBStates[NewRetainRelease->getParent()]; | |
2396 | unsigned PathCount = BBState::OverflowOccurredValue; | |
2397 | if (NRRBBState.GetAllPathCountWithOverflow(PathCount)) | |
2398 | return false; | |
2399 | assert(PathCount != BBState::OverflowOccurredValue && | |
2400 | "PathCount at this point can not be " | |
2401 | "OverflowOccurredValue."); | |
2402 | OldDelta -= PathCount; | |
970d7e83 LB |
2403 | |
2404 | // Merge the ReleaseMetadata and IsTailCallRelease values. | |
2405 | if (FirstRelease) { | |
2406 | ReleasesToMove.ReleaseMetadata = | |
2407 | NewRetainReleaseRRI.ReleaseMetadata; | |
2408 | ReleasesToMove.IsTailCallRelease = | |
2409 | NewRetainReleaseRRI.IsTailCallRelease; | |
2410 | FirstRelease = false; | |
2411 | } else { | |
2412 | if (ReleasesToMove.ReleaseMetadata != | |
2413 | NewRetainReleaseRRI.ReleaseMetadata) | |
1a4d82fc | 2414 | ReleasesToMove.ReleaseMetadata = nullptr; |
970d7e83 LB |
2415 | if (ReleasesToMove.IsTailCallRelease != |
2416 | NewRetainReleaseRRI.IsTailCallRelease) | |
2417 | ReleasesToMove.IsTailCallRelease = false; | |
2418 | } | |
2419 | ||
2420 | // Collect the optimal insertion points. | |
2421 | if (!KnownSafe) | |
1a4d82fc | 2422 | for (Instruction *RIP : NewRetainReleaseRRI.ReverseInsertPts) { |
85aaf69f | 2423 | if (ReleasesToMove.ReverseInsertPts.insert(RIP).second) { |
1a4d82fc JJ |
2424 | // If we overflow when we compute the path count, don't |
2425 | // remove/move anything. | |
2426 | const BBState &RIPBBState = BBStates[RIP->getParent()]; | |
2427 | PathCount = BBState::OverflowOccurredValue; | |
2428 | if (RIPBBState.GetAllPathCountWithOverflow(PathCount)) | |
2429 | return false; | |
2430 | assert(PathCount != BBState::OverflowOccurredValue && | |
2431 | "PathCount at this point can not be " | |
2432 | "OverflowOccurredValue."); | |
2433 | NewDelta -= PathCount; | |
2434 | } | |
970d7e83 LB |
2435 | } |
2436 | NewReleases.push_back(NewRetainRelease); | |
2437 | } | |
2438 | } | |
2439 | } | |
2440 | NewRetains.clear(); | |
2441 | if (NewReleases.empty()) break; | |
2442 | ||
2443 | // Back the other way. | |
2444 | for (SmallVectorImpl<Instruction *>::const_iterator | |
2445 | NI = NewReleases.begin(), NE = NewReleases.end(); NI != NE; ++NI) { | |
2446 | Instruction *NewRelease = *NI; | |
2447 | DenseMap<Value *, RRInfo>::const_iterator It = | |
2448 | Releases.find(NewRelease); | |
2449 | assert(It != Releases.end()); | |
2450 | const RRInfo &NewReleaseRRI = It->second; | |
2451 | KnownSafeBU &= NewReleaseRRI.KnownSafe; | |
1a4d82fc JJ |
2452 | CFGHazardAfflicted |= NewReleaseRRI.CFGHazardAfflicted; |
2453 | for (Instruction *NewReleaseRetain : NewReleaseRRI.Calls) { | |
970d7e83 LB |
2454 | MapVector<Value *, RRInfo>::const_iterator Jt = |
2455 | Retains.find(NewReleaseRetain); | |
2456 | if (Jt == Retains.end()) | |
2457 | return false; | |
2458 | const RRInfo &NewReleaseRetainRRI = Jt->second; | |
1a4d82fc JJ |
2459 | |
2460 | // If the retain does not have a reference to the release as well, | |
2461 | // something happened which is unaccounted for. Do not do anything. | |
2462 | // | |
2463 | // This can happen if we catch an additive overflow during path count | |
2464 | // merging. | |
2465 | if (!NewReleaseRetainRRI.Calls.count(NewRelease)) | |
2466 | return false; | |
2467 | ||
85aaf69f | 2468 | if (RetainsToMove.Calls.insert(NewReleaseRetain).second) { |
1a4d82fc JJ |
2469 | // If we overflow when we compute the path count, don't remove/move |
2470 | // anything. | |
2471 | const BBState &NRRBBState = BBStates[NewReleaseRetain->getParent()]; | |
2472 | unsigned PathCount = BBState::OverflowOccurredValue; | |
2473 | if (NRRBBState.GetAllPathCountWithOverflow(PathCount)) | |
2474 | return false; | |
2475 | assert(PathCount != BBState::OverflowOccurredValue && | |
2476 | "PathCount at this point can not be " | |
2477 | "OverflowOccurredValue."); | |
970d7e83 LB |
2478 | OldDelta += PathCount; |
2479 | OldCount += PathCount; | |
2480 | ||
970d7e83 LB |
2481 | // Collect the optimal insertion points. |
2482 | if (!KnownSafe) | |
1a4d82fc | 2483 | for (Instruction *RIP : NewReleaseRetainRRI.ReverseInsertPts) { |
85aaf69f | 2484 | if (RetainsToMove.ReverseInsertPts.insert(RIP).second) { |
1a4d82fc JJ |
2485 | // If we overflow when we compute the path count, don't |
2486 | // remove/move anything. | |
2487 | const BBState &RIPBBState = BBStates[RIP->getParent()]; | |
2488 | ||
2489 | PathCount = BBState::OverflowOccurredValue; | |
2490 | if (RIPBBState.GetAllPathCountWithOverflow(PathCount)) | |
2491 | return false; | |
2492 | assert(PathCount != BBState::OverflowOccurredValue && | |
2493 | "PathCount at this point can not be " | |
2494 | "OverflowOccurredValue."); | |
970d7e83 LB |
2495 | NewDelta += PathCount; |
2496 | NewCount += PathCount; | |
2497 | } | |
2498 | } | |
2499 | NewRetains.push_back(NewReleaseRetain); | |
2500 | } | |
2501 | } | |
2502 | } | |
2503 | NewReleases.clear(); | |
2504 | if (NewRetains.empty()) break; | |
2505 | } | |
2506 | ||
1a4d82fc JJ |
2507 | // If the pointer is known incremented in 1 direction and we do not have |
2508 | // MultipleOwners, we can safely remove the retain/releases. Otherwise we need | |
2509 | // to be known safe in both directions. | |
2510 | bool UnconditionallySafe = (KnownSafeTD && KnownSafeBU) || | |
2511 | ((KnownSafeTD || KnownSafeBU) && !MultipleOwners); | |
2512 | if (UnconditionallySafe) { | |
970d7e83 LB |
2513 | RetainsToMove.ReverseInsertPts.clear(); |
2514 | ReleasesToMove.ReverseInsertPts.clear(); | |
2515 | NewCount = 0; | |
2516 | } else { | |
2517 | // Determine whether the new insertion points we computed preserve the | |
2518 | // balance of retain and release calls through the program. | |
2519 | // TODO: If the fully aggressive solution isn't valid, try to find a | |
2520 | // less aggressive solution which is. | |
2521 | if (NewDelta != 0) | |
2522 | return false; | |
1a4d82fc JJ |
2523 | |
2524 | // At this point, we are not going to remove any RR pairs, but we still are | |
2525 | // able to move RR pairs. If one of our pointers is afflicted with | |
2526 | // CFGHazards, we cannot perform such code motion so exit early. | |
2527 | const bool WillPerformCodeMotion = RetainsToMove.ReverseInsertPts.size() || | |
2528 | ReleasesToMove.ReverseInsertPts.size(); | |
2529 | if (CFGHazardAfflicted && WillPerformCodeMotion) | |
2530 | return false; | |
970d7e83 LB |
2531 | } |
2532 | ||
2533 | // Determine whether the original call points are balanced in the retain and | |
2534 | // release calls through the program. If not, conservatively don't touch | |
2535 | // them. | |
2536 | // TODO: It's theoretically possible to do code motion in this case, as | |
2537 | // long as the existing imbalances are maintained. | |
2538 | if (OldDelta != 0) | |
2539 | return false; | |
2540 | ||
1a4d82fc JJ |
2541 | #ifdef ARC_ANNOTATIONS |
2542 | // Do not move calls if ARC annotations are requested. | |
2543 | if (EnableARCAnnotations) | |
2544 | return false; | |
2545 | #endif // ARC_ANNOTATIONS | |
2546 | ||
970d7e83 LB |
2547 | Changed = true; |
2548 | assert(OldCount != 0 && "Unreachable code?"); | |
2549 | NumRRs += OldCount - NewCount; | |
2550 | // Set to true if we completely removed any RR pairs. | |
2551 | AnyPairsCompletelyEliminated = NewCount == 0; | |
2552 | ||
2553 | // We can move calls! | |
2554 | return true; | |
2555 | } | |
2556 | ||
2557 | /// Identify pairings between the retains and releases, and delete and/or move | |
2558 | /// them. | |
2559 | bool | |
2560 | ObjCARCOpt::PerformCodePlacement(DenseMap<const BasicBlock *, BBState> | |
2561 | &BBStates, | |
2562 | MapVector<Value *, RRInfo> &Retains, | |
2563 | DenseMap<Value *, RRInfo> &Releases, | |
2564 | Module *M) { | |
1a4d82fc JJ |
2565 | DEBUG(dbgs() << "\n== ObjCARCOpt::PerformCodePlacement ==\n"); |
2566 | ||
970d7e83 LB |
2567 | bool AnyPairsCompletelyEliminated = false; |
2568 | RRInfo RetainsToMove; | |
2569 | RRInfo ReleasesToMove; | |
2570 | SmallVector<Instruction *, 4> NewRetains; | |
2571 | SmallVector<Instruction *, 4> NewReleases; | |
2572 | SmallVector<Instruction *, 8> DeadInsts; | |
2573 | ||
2574 | // Visit each retain. | |
2575 | for (MapVector<Value *, RRInfo>::const_iterator I = Retains.begin(), | |
2576 | E = Retains.end(); I != E; ++I) { | |
2577 | Value *V = I->first; | |
2578 | if (!V) continue; // blotted | |
2579 | ||
2580 | Instruction *Retain = cast<Instruction>(V); | |
2581 | ||
1a4d82fc | 2582 | DEBUG(dbgs() << "Visiting: " << *Retain << "\n"); |
970d7e83 LB |
2583 | |
2584 | Value *Arg = GetObjCArg(Retain); | |
2585 | ||
2586 | // If the object being released is in static or stack storage, we know it's | |
2587 | // not being managed by ObjC reference counting, so we can delete pairs | |
2588 | // regardless of what possible decrements or uses lie between them. | |
2589 | bool KnownSafe = isa<Constant>(Arg) || isa<AllocaInst>(Arg); | |
2590 | ||
2591 | // A constant pointer can't be pointing to an object on the heap. It may | |
2592 | // be reference-counted, but it won't be deleted. | |
2593 | if (const LoadInst *LI = dyn_cast<LoadInst>(Arg)) | |
2594 | if (const GlobalVariable *GV = | |
2595 | dyn_cast<GlobalVariable>( | |
2596 | StripPointerCastsAndObjCCalls(LI->getPointerOperand()))) | |
2597 | if (GV->isConstant()) | |
2598 | KnownSafe = true; | |
2599 | ||
2600 | // Connect the dots between the top-down-collected RetainsToMove and | |
2601 | // bottom-up-collected ReleasesToMove to form sets of related calls. | |
2602 | NewRetains.push_back(Retain); | |
2603 | bool PerformMoveCalls = | |
2604 | ConnectTDBUTraversals(BBStates, Retains, Releases, M, NewRetains, | |
2605 | NewReleases, DeadInsts, RetainsToMove, | |
2606 | ReleasesToMove, Arg, KnownSafe, | |
2607 | AnyPairsCompletelyEliminated); | |
2608 | ||
2609 | if (PerformMoveCalls) { | |
2610 | // Ok, everything checks out and we're all set. Let's move/delete some | |
2611 | // code! | |
2612 | MoveCalls(Arg, RetainsToMove, ReleasesToMove, | |
2613 | Retains, Releases, DeadInsts, M); | |
2614 | } | |
2615 | ||
2616 | // Clean up state for next retain. | |
2617 | NewReleases.clear(); | |
2618 | NewRetains.clear(); | |
2619 | RetainsToMove.clear(); | |
2620 | ReleasesToMove.clear(); | |
2621 | } | |
2622 | ||
2623 | // Now that we're done moving everything, we can delete the newly dead | |
2624 | // instructions, as we no longer need them as insert points. | |
2625 | while (!DeadInsts.empty()) | |
2626 | EraseInstruction(DeadInsts.pop_back_val()); | |
2627 | ||
2628 | return AnyPairsCompletelyEliminated; | |
2629 | } | |
2630 | ||
2631 | /// Weak pointer optimizations. | |
2632 | void ObjCARCOpt::OptimizeWeakCalls(Function &F) { | |
1a4d82fc JJ |
2633 | DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeWeakCalls ==\n"); |
2634 | ||
970d7e83 LB |
2635 | // First, do memdep-style RLE and S2L optimizations. We can't use memdep |
2636 | // itself because it uses AliasAnalysis and we need to do provenance | |
2637 | // queries instead. | |
2638 | for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) { | |
2639 | Instruction *Inst = &*I++; | |
2640 | ||
1a4d82fc | 2641 | DEBUG(dbgs() << "Visiting: " << *Inst << "\n"); |
970d7e83 LB |
2642 | |
2643 | InstructionClass Class = GetBasicInstructionClass(Inst); | |
2644 | if (Class != IC_LoadWeak && Class != IC_LoadWeakRetained) | |
2645 | continue; | |
2646 | ||
2647 | // Delete objc_loadWeak calls with no users. | |
2648 | if (Class == IC_LoadWeak && Inst->use_empty()) { | |
2649 | Inst->eraseFromParent(); | |
2650 | continue; | |
2651 | } | |
2652 | ||
2653 | // TODO: For now, just look for an earlier available version of this value | |
2654 | // within the same block. Theoretically, we could do memdep-style non-local | |
2655 | // analysis too, but that would want caching. A better approach would be to | |
2656 | // use the technique that EarlyCSE uses. | |
1a4d82fc | 2657 | inst_iterator Current = std::prev(I); |
970d7e83 LB |
2658 | BasicBlock *CurrentBB = Current.getBasicBlockIterator(); |
2659 | for (BasicBlock::iterator B = CurrentBB->begin(), | |
2660 | J = Current.getInstructionIterator(); | |
2661 | J != B; --J) { | |
1a4d82fc | 2662 | Instruction *EarlierInst = &*std::prev(J); |
970d7e83 LB |
2663 | InstructionClass EarlierClass = GetInstructionClass(EarlierInst); |
2664 | switch (EarlierClass) { | |
2665 | case IC_LoadWeak: | |
2666 | case IC_LoadWeakRetained: { | |
2667 | // If this is loading from the same pointer, replace this load's value | |
2668 | // with that one. | |
2669 | CallInst *Call = cast<CallInst>(Inst); | |
2670 | CallInst *EarlierCall = cast<CallInst>(EarlierInst); | |
2671 | Value *Arg = Call->getArgOperand(0); | |
2672 | Value *EarlierArg = EarlierCall->getArgOperand(0); | |
2673 | switch (PA.getAA()->alias(Arg, EarlierArg)) { | |
2674 | case AliasAnalysis::MustAlias: | |
2675 | Changed = true; | |
2676 | // If the load has a builtin retain, insert a plain retain for it. | |
2677 | if (Class == IC_LoadWeakRetained) { | |
1a4d82fc JJ |
2678 | Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_Retain); |
2679 | CallInst *CI = CallInst::Create(Decl, EarlierCall, "", Call); | |
970d7e83 LB |
2680 | CI->setTailCall(); |
2681 | } | |
2682 | // Zap the fully redundant load. | |
2683 | Call->replaceAllUsesWith(EarlierCall); | |
2684 | Call->eraseFromParent(); | |
2685 | goto clobbered; | |
2686 | case AliasAnalysis::MayAlias: | |
2687 | case AliasAnalysis::PartialAlias: | |
2688 | goto clobbered; | |
2689 | case AliasAnalysis::NoAlias: | |
2690 | break; | |
2691 | } | |
2692 | break; | |
2693 | } | |
2694 | case IC_StoreWeak: | |
2695 | case IC_InitWeak: { | |
2696 | // If this is storing to the same pointer and has the same size etc. | |
2697 | // replace this load's value with the stored value. | |
2698 | CallInst *Call = cast<CallInst>(Inst); | |
2699 | CallInst *EarlierCall = cast<CallInst>(EarlierInst); | |
2700 | Value *Arg = Call->getArgOperand(0); | |
2701 | Value *EarlierArg = EarlierCall->getArgOperand(0); | |
2702 | switch (PA.getAA()->alias(Arg, EarlierArg)) { | |
2703 | case AliasAnalysis::MustAlias: | |
2704 | Changed = true; | |
2705 | // If the load has a builtin retain, insert a plain retain for it. | |
2706 | if (Class == IC_LoadWeakRetained) { | |
1a4d82fc JJ |
2707 | Constant *Decl = EP.get(ARCRuntimeEntryPoints::EPT_Retain); |
2708 | CallInst *CI = CallInst::Create(Decl, EarlierCall, "", Call); | |
970d7e83 LB |
2709 | CI->setTailCall(); |
2710 | } | |
2711 | // Zap the fully redundant load. | |
2712 | Call->replaceAllUsesWith(EarlierCall->getArgOperand(1)); | |
2713 | Call->eraseFromParent(); | |
2714 | goto clobbered; | |
2715 | case AliasAnalysis::MayAlias: | |
2716 | case AliasAnalysis::PartialAlias: | |
2717 | goto clobbered; | |
2718 | case AliasAnalysis::NoAlias: | |
2719 | break; | |
2720 | } | |
2721 | break; | |
2722 | } | |
2723 | case IC_MoveWeak: | |
2724 | case IC_CopyWeak: | |
2725 | // TOOD: Grab the copied value. | |
2726 | goto clobbered; | |
2727 | case IC_AutoreleasepoolPush: | |
2728 | case IC_None: | |
1a4d82fc | 2729 | case IC_IntrinsicUser: |
970d7e83 LB |
2730 | case IC_User: |
2731 | // Weak pointers are only modified through the weak entry points | |
2732 | // (and arbitrary calls, which could call the weak entry points). | |
2733 | break; | |
2734 | default: | |
2735 | // Anything else could modify the weak pointer. | |
2736 | goto clobbered; | |
2737 | } | |
2738 | } | |
2739 | clobbered:; | |
2740 | } | |
2741 | ||
2742 | // Then, for each destroyWeak with an alloca operand, check to see if | |
2743 | // the alloca and all its users can be zapped. | |
2744 | for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) { | |
2745 | Instruction *Inst = &*I++; | |
2746 | InstructionClass Class = GetBasicInstructionClass(Inst); | |
2747 | if (Class != IC_DestroyWeak) | |
2748 | continue; | |
2749 | ||
2750 | CallInst *Call = cast<CallInst>(Inst); | |
2751 | Value *Arg = Call->getArgOperand(0); | |
2752 | if (AllocaInst *Alloca = dyn_cast<AllocaInst>(Arg)) { | |
1a4d82fc JJ |
2753 | for (User *U : Alloca->users()) { |
2754 | const Instruction *UserInst = cast<Instruction>(U); | |
970d7e83 LB |
2755 | switch (GetBasicInstructionClass(UserInst)) { |
2756 | case IC_InitWeak: | |
2757 | case IC_StoreWeak: | |
2758 | case IC_DestroyWeak: | |
2759 | continue; | |
2760 | default: | |
2761 | goto done; | |
2762 | } | |
2763 | } | |
2764 | Changed = true; | |
1a4d82fc | 2765 | for (auto UI = Alloca->user_begin(), UE = Alloca->user_end(); UI != UE;) { |
970d7e83 LB |
2766 | CallInst *UserInst = cast<CallInst>(*UI++); |
2767 | switch (GetBasicInstructionClass(UserInst)) { | |
2768 | case IC_InitWeak: | |
2769 | case IC_StoreWeak: | |
2770 | // These functions return their second argument. | |
2771 | UserInst->replaceAllUsesWith(UserInst->getArgOperand(1)); | |
2772 | break; | |
2773 | case IC_DestroyWeak: | |
2774 | // No return value. | |
2775 | break; | |
2776 | default: | |
2777 | llvm_unreachable("alloca really is used!"); | |
2778 | } | |
2779 | UserInst->eraseFromParent(); | |
2780 | } | |
2781 | Alloca->eraseFromParent(); | |
2782 | done:; | |
2783 | } | |
2784 | } | |
970d7e83 LB |
2785 | } |
2786 | ||
2787 | /// Identify program paths which execute sequences of retains and releases which | |
2788 | /// can be eliminated. | |
2789 | bool ObjCARCOpt::OptimizeSequences(Function &F) { | |
1a4d82fc JJ |
2790 | // Releases, Retains - These are used to store the results of the main flow |
2791 | // analysis. These use Value* as the key instead of Instruction* so that the | |
2792 | // map stays valid when we get around to rewriting code and calls get | |
2793 | // replaced by arguments. | |
970d7e83 LB |
2794 | DenseMap<Value *, RRInfo> Releases; |
2795 | MapVector<Value *, RRInfo> Retains; | |
2796 | ||
1a4d82fc JJ |
2797 | // This is used during the traversal of the function to track the |
2798 | // states for each identified object at each block. | |
970d7e83 LB |
2799 | DenseMap<const BasicBlock *, BBState> BBStates; |
2800 | ||
2801 | // Analyze the CFG of the function, and all instructions. | |
2802 | bool NestingDetected = Visit(F, BBStates, Retains, Releases); | |
2803 | ||
2804 | // Transform. | |
1a4d82fc JJ |
2805 | bool AnyPairsCompletelyEliminated = PerformCodePlacement(BBStates, Retains, |
2806 | Releases, | |
2807 | F.getParent()); | |
2808 | ||
2809 | // Cleanup. | |
2810 | MultiOwnersSet.clear(); | |
2811 | ||
2812 | return AnyPairsCompletelyEliminated && NestingDetected; | |
2813 | } | |
2814 | ||
2815 | /// Check if there is a dependent call earlier that does not have anything in | |
2816 | /// between the Retain and the call that can affect the reference count of their | |
2817 | /// shared pointer argument. Note that Retain need not be in BB. | |
2818 | static bool | |
2819 | HasSafePathToPredecessorCall(const Value *Arg, Instruction *Retain, | |
2820 | SmallPtrSetImpl<Instruction *> &DepInsts, | |
2821 | SmallPtrSetImpl<const BasicBlock *> &Visited, | |
2822 | ProvenanceAnalysis &PA) { | |
2823 | FindDependencies(CanChangeRetainCount, Arg, Retain->getParent(), Retain, | |
2824 | DepInsts, Visited, PA); | |
2825 | if (DepInsts.size() != 1) | |
2826 | return false; | |
2827 | ||
2828 | CallInst *Call = | |
2829 | dyn_cast_or_null<CallInst>(*DepInsts.begin()); | |
2830 | ||
2831 | // Check that the pointer is the return value of the call. | |
2832 | if (!Call || Arg != Call) | |
2833 | return false; | |
2834 | ||
2835 | // Check that the call is a regular call. | |
2836 | InstructionClass Class = GetBasicInstructionClass(Call); | |
2837 | if (Class != IC_CallOrUser && Class != IC_Call) | |
2838 | return false; | |
2839 | ||
2840 | return true; | |
2841 | } | |
2842 | ||
2843 | /// Find a dependent retain that precedes the given autorelease for which there | |
2844 | /// is nothing in between the two instructions that can affect the ref count of | |
2845 | /// Arg. | |
2846 | static CallInst * | |
2847 | FindPredecessorRetainWithSafePath(const Value *Arg, BasicBlock *BB, | |
2848 | Instruction *Autorelease, | |
2849 | SmallPtrSetImpl<Instruction *> &DepInsts, | |
2850 | SmallPtrSetImpl<const BasicBlock *> &Visited, | |
2851 | ProvenanceAnalysis &PA) { | |
2852 | FindDependencies(CanChangeRetainCount, Arg, | |
2853 | BB, Autorelease, DepInsts, Visited, PA); | |
2854 | if (DepInsts.size() != 1) | |
2855 | return nullptr; | |
2856 | ||
2857 | CallInst *Retain = | |
2858 | dyn_cast_or_null<CallInst>(*DepInsts.begin()); | |
2859 | ||
2860 | // Check that we found a retain with the same argument. | |
2861 | if (!Retain || | |
2862 | !IsRetain(GetBasicInstructionClass(Retain)) || | |
2863 | GetObjCArg(Retain) != Arg) { | |
2864 | return nullptr; | |
2865 | } | |
2866 | ||
2867 | return Retain; | |
2868 | } | |
2869 | ||
2870 | /// Look for an ``autorelease'' instruction dependent on Arg such that there are | |
2871 | /// no instructions dependent on Arg that need a positive ref count in between | |
2872 | /// the autorelease and the ret. | |
2873 | static CallInst * | |
2874 | FindPredecessorAutoreleaseWithSafePath(const Value *Arg, BasicBlock *BB, | |
2875 | ReturnInst *Ret, | |
2876 | SmallPtrSetImpl<Instruction *> &DepInsts, | |
2877 | SmallPtrSetImpl<const BasicBlock *> &V, | |
2878 | ProvenanceAnalysis &PA) { | |
2879 | FindDependencies(NeedsPositiveRetainCount, Arg, | |
2880 | BB, Ret, DepInsts, V, PA); | |
2881 | if (DepInsts.size() != 1) | |
2882 | return nullptr; | |
2883 | ||
2884 | CallInst *Autorelease = | |
2885 | dyn_cast_or_null<CallInst>(*DepInsts.begin()); | |
2886 | if (!Autorelease) | |
2887 | return nullptr; | |
2888 | InstructionClass AutoreleaseClass = GetBasicInstructionClass(Autorelease); | |
2889 | if (!IsAutorelease(AutoreleaseClass)) | |
2890 | return nullptr; | |
2891 | if (GetObjCArg(Autorelease) != Arg) | |
2892 | return nullptr; | |
2893 | ||
2894 | return Autorelease; | |
970d7e83 LB |
2895 | } |
2896 | ||
2897 | /// Look for this pattern: | |
2898 | /// \code | |
2899 | /// %call = call i8* @something(...) | |
2900 | /// %2 = call i8* @objc_retain(i8* %call) | |
2901 | /// %3 = call i8* @objc_autorelease(i8* %2) | |
2902 | /// ret i8* %3 | |
2903 | /// \endcode | |
2904 | /// And delete the retain and autorelease. | |
970d7e83 LB |
2905 | void ObjCARCOpt::OptimizeReturns(Function &F) { |
2906 | if (!F.getReturnType()->isPointerTy()) | |
2907 | return; | |
2908 | ||
1a4d82fc JJ |
2909 | DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeReturns ==\n"); |
2910 | ||
970d7e83 LB |
2911 | SmallPtrSet<Instruction *, 4> DependingInstructions; |
2912 | SmallPtrSet<const BasicBlock *, 4> Visited; | |
2913 | for (Function::iterator FI = F.begin(), FE = F.end(); FI != FE; ++FI) { | |
2914 | BasicBlock *BB = FI; | |
2915 | ReturnInst *Ret = dyn_cast<ReturnInst>(&BB->back()); | |
2916 | ||
1a4d82fc | 2917 | DEBUG(dbgs() << "Visiting: " << *Ret << "\n"); |
970d7e83 | 2918 | |
1a4d82fc JJ |
2919 | if (!Ret) |
2920 | continue; | |
970d7e83 LB |
2921 | |
2922 | const Value *Arg = StripPointerCastsAndObjCCalls(Ret->getOperand(0)); | |
970d7e83 | 2923 | |
1a4d82fc JJ |
2924 | // Look for an ``autorelease'' instruction that is a predecessor of Ret and |
2925 | // dependent on Arg such that there are no instructions dependent on Arg | |
2926 | // that need a positive ref count in between the autorelease and Ret. | |
2927 | CallInst *Autorelease = | |
2928 | FindPredecessorAutoreleaseWithSafePath(Arg, BB, Ret, | |
2929 | DependingInstructions, Visited, | |
2930 | PA); | |
2931 | DependingInstructions.clear(); | |
2932 | Visited.clear(); | |
970d7e83 | 2933 | |
1a4d82fc JJ |
2934 | if (!Autorelease) |
2935 | continue; | |
970d7e83 | 2936 | |
1a4d82fc JJ |
2937 | CallInst *Retain = |
2938 | FindPredecessorRetainWithSafePath(Arg, BB, Autorelease, | |
2939 | DependingInstructions, Visited, PA); | |
2940 | DependingInstructions.clear(); | |
2941 | Visited.clear(); | |
970d7e83 | 2942 | |
1a4d82fc JJ |
2943 | if (!Retain) |
2944 | continue; | |
970d7e83 | 2945 | |
1a4d82fc JJ |
2946 | // Check that there is nothing that can affect the reference count |
2947 | // between the retain and the call. Note that Retain need not be in BB. | |
2948 | bool HasSafePathToCall = HasSafePathToPredecessorCall(Arg, Retain, | |
2949 | DependingInstructions, | |
2950 | Visited, PA); | |
970d7e83 LB |
2951 | DependingInstructions.clear(); |
2952 | Visited.clear(); | |
1a4d82fc JJ |
2953 | |
2954 | if (!HasSafePathToCall) | |
2955 | continue; | |
2956 | ||
2957 | // If so, we can zap the retain and autorelease. | |
2958 | Changed = true; | |
2959 | ++NumRets; | |
2960 | DEBUG(dbgs() << "Erasing: " << *Retain << "\nErasing: " | |
2961 | << *Autorelease << "\n"); | |
2962 | EraseInstruction(Retain); | |
2963 | EraseInstruction(Autorelease); | |
970d7e83 | 2964 | } |
1a4d82fc | 2965 | } |
970d7e83 | 2966 | |
1a4d82fc JJ |
2967 | #ifndef NDEBUG |
2968 | void | |
2969 | ObjCARCOpt::GatherStatistics(Function &F, bool AfterOptimization) { | |
2970 | llvm::Statistic &NumRetains = | |
2971 | AfterOptimization? NumRetainsAfterOpt : NumRetainsBeforeOpt; | |
2972 | llvm::Statistic &NumReleases = | |
2973 | AfterOptimization? NumReleasesAfterOpt : NumReleasesBeforeOpt; | |
970d7e83 | 2974 | |
1a4d82fc JJ |
2975 | for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) { |
2976 | Instruction *Inst = &*I++; | |
2977 | switch (GetBasicInstructionClass(Inst)) { | |
2978 | default: | |
2979 | break; | |
2980 | case IC_Retain: | |
2981 | ++NumRetains; | |
2982 | break; | |
2983 | case IC_Release: | |
2984 | ++NumReleases; | |
2985 | break; | |
2986 | } | |
2987 | } | |
970d7e83 | 2988 | } |
1a4d82fc | 2989 | #endif |
970d7e83 LB |
2990 | |
2991 | bool ObjCARCOpt::doInitialization(Module &M) { | |
2992 | if (!EnableARCOpts) | |
2993 | return false; | |
2994 | ||
2995 | // If nothing in the Module uses ARC, don't do anything. | |
2996 | Run = ModuleHasARC(M); | |
2997 | if (!Run) | |
2998 | return false; | |
2999 | ||
3000 | // Identify the imprecise release metadata kind. | |
3001 | ImpreciseReleaseMDKind = | |
3002 | M.getContext().getMDKindID("clang.imprecise_release"); | |
3003 | CopyOnEscapeMDKind = | |
3004 | M.getContext().getMDKindID("clang.arc.copy_on_escape"); | |
3005 | NoObjCARCExceptionsMDKind = | |
3006 | M.getContext().getMDKindID("clang.arc.no_objc_arc_exceptions"); | |
1a4d82fc JJ |
3007 | #ifdef ARC_ANNOTATIONS |
3008 | ARCAnnotationBottomUpMDKind = | |
3009 | M.getContext().getMDKindID("llvm.arc.annotation.bottomup"); | |
3010 | ARCAnnotationTopDownMDKind = | |
3011 | M.getContext().getMDKindID("llvm.arc.annotation.topdown"); | |
3012 | ARCAnnotationProvenanceSourceMDKind = | |
3013 | M.getContext().getMDKindID("llvm.arc.annotation.provenancesource"); | |
3014 | #endif // ARC_ANNOTATIONS | |
970d7e83 LB |
3015 | |
3016 | // Intuitively, objc_retain and others are nocapture, however in practice | |
3017 | // they are not, because they return their argument value. And objc_release | |
3018 | // calls finalizers which can have arbitrary side effects. | |
3019 | ||
1a4d82fc JJ |
3020 | // Initialize our runtime entry point cache. |
3021 | EP.Initialize(&M); | |
970d7e83 LB |
3022 | |
3023 | return false; | |
3024 | } | |
3025 | ||
3026 | bool ObjCARCOpt::runOnFunction(Function &F) { | |
3027 | if (!EnableARCOpts) | |
3028 | return false; | |
3029 | ||
3030 | // If nothing in the Module uses ARC, don't do anything. | |
3031 | if (!Run) | |
3032 | return false; | |
3033 | ||
3034 | Changed = false; | |
3035 | ||
1a4d82fc JJ |
3036 | DEBUG(dbgs() << "<<< ObjCARCOpt: Visiting Function: " << F.getName() << " >>>" |
3037 | "\n"); | |
970d7e83 LB |
3038 | |
3039 | PA.setAA(&getAnalysis<AliasAnalysis>()); | |
3040 | ||
1a4d82fc JJ |
3041 | #ifndef NDEBUG |
3042 | if (AreStatisticsEnabled()) { | |
3043 | GatherStatistics(F, false); | |
3044 | } | |
3045 | #endif | |
3046 | ||
970d7e83 LB |
3047 | // This pass performs several distinct transformations. As a compile-time aid |
3048 | // when compiling code that isn't ObjC, skip these if the relevant ObjC | |
3049 | // library functions aren't declared. | |
3050 | ||
1a4d82fc | 3051 | // Preliminary optimizations. This also computes UsedInThisFunction. |
970d7e83 LB |
3052 | OptimizeIndividualCalls(F); |
3053 | ||
3054 | // Optimizations for weak pointers. | |
3055 | if (UsedInThisFunction & ((1 << IC_LoadWeak) | | |
3056 | (1 << IC_LoadWeakRetained) | | |
3057 | (1 << IC_StoreWeak) | | |
3058 | (1 << IC_InitWeak) | | |
3059 | (1 << IC_CopyWeak) | | |
3060 | (1 << IC_MoveWeak) | | |
3061 | (1 << IC_DestroyWeak))) | |
3062 | OptimizeWeakCalls(F); | |
3063 | ||
3064 | // Optimizations for retain+release pairs. | |
3065 | if (UsedInThisFunction & ((1 << IC_Retain) | | |
3066 | (1 << IC_RetainRV) | | |
3067 | (1 << IC_RetainBlock))) | |
3068 | if (UsedInThisFunction & (1 << IC_Release)) | |
3069 | // Run OptimizeSequences until it either stops making changes or | |
3070 | // no retain+release pair nesting is detected. | |
3071 | while (OptimizeSequences(F)) {} | |
3072 | ||
3073 | // Optimizations if objc_autorelease is used. | |
3074 | if (UsedInThisFunction & ((1 << IC_Autorelease) | | |
3075 | (1 << IC_AutoreleaseRV))) | |
3076 | OptimizeReturns(F); | |
3077 | ||
1a4d82fc JJ |
3078 | // Gather statistics after optimization. |
3079 | #ifndef NDEBUG | |
3080 | if (AreStatisticsEnabled()) { | |
3081 | GatherStatistics(F, true); | |
3082 | } | |
3083 | #endif | |
3084 | ||
970d7e83 LB |
3085 | DEBUG(dbgs() << "\n"); |
3086 | ||
3087 | return Changed; | |
3088 | } | |
3089 | ||
3090 | void ObjCARCOpt::releaseMemory() { | |
3091 | PA.clear(); | |
3092 | } | |
3093 | ||
3094 | /// @} | |
3095 | /// |