1//===- ObjCARCOpts.cpp - ObjC ARC Optimization ----------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9/// \file
10/// 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
27#include "ARCRuntimeEntryPoints.h"
28#include "BlotMapVector.h"
29#include "DependencyAnalysis.h"
30#include "ObjCARC.h"
31#include "ProvenanceAnalysis.h"
32#include "PtrState.h"
33#include "llvm/ADT/DenseMap.h"
34#include "llvm/ADT/STLExtras.h"
35#include "llvm/ADT/SmallPtrSet.h"
36#include "llvm/ADT/SmallVector.h"
37#include "llvm/ADT/Statistic.h"
38#include "llvm/Analysis/AliasAnalysis.h"
39#include "llvm/Analysis/ObjCARCAnalysisUtils.h"
40#include "llvm/Analysis/ObjCARCInstKind.h"
41#include "llvm/Analysis/ObjCARCUtil.h"
42#include "llvm/Analysis/OptimizationRemarkEmitter.h"
43#include "llvm/IR/BasicBlock.h"
44#include "llvm/IR/CFG.h"
45#include "llvm/IR/Constant.h"
46#include "llvm/IR/Constants.h"
47#include "llvm/IR/DerivedTypes.h"
48#include "llvm/IR/EHPersonalities.h"
49#include "llvm/IR/Function.h"
50#include "llvm/IR/GlobalVariable.h"
51#include "llvm/IR/InstIterator.h"
52#include "llvm/IR/InstrTypes.h"
53#include "llvm/IR/Instruction.h"
54#include "llvm/IR/Instructions.h"
55#include "llvm/IR/LLVMContext.h"
56#include "llvm/IR/Metadata.h"
57#include "llvm/IR/Type.h"
58#include "llvm/IR/User.h"
59#include "llvm/IR/Value.h"
60#include "llvm/Support/Casting.h"
61#include "llvm/Support/CommandLine.h"
62#include "llvm/Support/Compiler.h"
63#include "llvm/Support/Debug.h"
64#include "llvm/Support/ErrorHandling.h"
65#include "llvm/Support/raw_ostream.h"
66#include "llvm/Transforms/ObjCARC.h"
67#include <cassert>
68#include <iterator>
69#include <utility>
70
71using namespace llvm;
72using namespace llvm::objcarc;
73
74#define DEBUG_TYPE "objc-arc-opts"
75
76static cl::opt<unsigned> MaxPtrStates("arc-opt-max-ptr-states",
77 cl::Hidden,
78 cl::desc("Maximum number of ptr states the optimizer keeps track of"),
79 cl::init(Val: 4095));
80
81/// \defgroup ARCUtilities Utility declarations/definitions specific to ARC.
82/// @{
83
84/// This is similar to GetRCIdentityRoot but it stops as soon
85/// as it finds a value with multiple uses.
86static const Value *FindSingleUseIdentifiedObject(const Value *Arg) {
87 // ConstantData (like ConstantPointerNull and UndefValue) is used across
88 // modules. It's never a single-use value.
89 if (isa<ConstantData>(Val: Arg))
90 return nullptr;
91
92 if (Arg->hasOneUse()) {
93 if (const BitCastInst *BC = dyn_cast<BitCastInst>(Val: Arg))
94 return FindSingleUseIdentifiedObject(Arg: BC->getOperand(i_nocapture: 0));
95 if (const GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Val: Arg))
96 if (GEP->hasAllZeroIndices())
97 return FindSingleUseIdentifiedObject(Arg: GEP->getPointerOperand());
98 if (IsForwarding(Class: GetBasicARCInstKind(V: Arg)))
99 return FindSingleUseIdentifiedObject(
100 Arg: cast<CallInst>(Val: Arg)->getArgOperand(i: 0));
101 if (!IsObjCIdentifiedObject(V: Arg))
102 return nullptr;
103 return Arg;
104 }
105
106 // If we found an identifiable object but it has multiple uses, but they are
107 // trivial uses, we can still consider this to be a single-use value.
108 if (IsObjCIdentifiedObject(V: Arg)) {
109 for (const User *U : Arg->users())
110 if (!U->use_empty() || GetRCIdentityRoot(V: U) != Arg)
111 return nullptr;
112
113 return Arg;
114 }
115
116 return nullptr;
117}
118
119/// @}
120///
121/// \defgroup ARCOpt ARC Optimization.
122/// @{
123
124// TODO: On code like this:
125//
126// objc_retain(%x)
127// stuff_that_cannot_release()
128// objc_autorelease(%x)
129// stuff_that_cannot_release()
130// objc_retain(%x)
131// stuff_that_cannot_release()
132// objc_autorelease(%x)
133//
134// The second retain and autorelease can be deleted.
135
136// TODO: Autorelease calls followed by objc_autoreleasePoolPop calls (perhaps in
137// ObjC++ code after inlining) can be turned into plain release calls.
138
139// TODO: Critical-edge splitting. If the optimial insertion point is
140// a critical edge, the current algorithm has to fail, because it doesn't
141// know how to split edges. It should be possible to make the optimizer
142// think in terms of edges, rather than blocks, and then split critical
143// edges on demand.
144
145// TODO: OptimizeSequences could generalized to be Interprocedural.
146
147// TODO: Recognize that a bunch of other objc runtime calls have
148// non-escaping arguments and non-releasing arguments, and may be
149// non-autoreleasing.
150
151// TODO: Sink autorelease calls as far as possible. Unfortunately we
152// usually can't sink them past other calls, which would be the main
153// case where it would be useful.
154
155// TODO: The pointer returned from objc_loadWeakRetained is retained.
156
157// TODO: Delete release+retain pairs (rare).
158
159STATISTIC(NumNoops, "Number of no-op objc calls eliminated");
160STATISTIC(NumPartialNoops, "Number of partially no-op objc calls eliminated");
161STATISTIC(NumAutoreleases,"Number of autoreleases converted to releases");
162STATISTIC(NumRets, "Number of return value forwarding "
163 "retain+autoreleases eliminated");
164STATISTIC(NumRRs, "Number of retain+release paths eliminated");
165STATISTIC(NumPeeps, "Number of calls peephole-optimized");
166#ifndef NDEBUG
167STATISTIC(NumRetainsBeforeOpt,
168 "Number of retains before optimization");
169STATISTIC(NumReleasesBeforeOpt,
170 "Number of releases before optimization");
171STATISTIC(NumRetainsAfterOpt,
172 "Number of retains after optimization");
173STATISTIC(NumReleasesAfterOpt,
174 "Number of releases after optimization");
175#endif
176
177namespace {
178
179 /// Per-BasicBlock state.
180 class BBState {
181 /// The number of unique control paths from the entry which can reach this
182 /// block.
183 unsigned TopDownPathCount = 0;
184
185 /// The number of unique control paths to exits from this block.
186 unsigned BottomUpPathCount = 0;
187
188 /// The top-down traversal uses this to record information known about a
189 /// pointer at the bottom of each block.
190 BlotMapVector<const Value *, TopDownPtrState> PerPtrTopDown;
191
192 /// The bottom-up traversal uses this to record information known about a
193 /// pointer at the top of each block.
194 BlotMapVector<const Value *, BottomUpPtrState> PerPtrBottomUp;
195
196 /// Effective predecessors of the current block ignoring ignorable edges and
197 /// ignored backedges.
198 SmallVector<BasicBlock *, 2> Preds;
199
200 /// Effective successors of the current block ignoring ignorable edges and
201 /// ignored backedges.
202 SmallVector<BasicBlock *, 2> Succs;
203
204 public:
205 static const unsigned OverflowOccurredValue;
206
207 BBState() = default;
208
209 using top_down_ptr_iterator = decltype(PerPtrTopDown)::iterator;
210 using const_top_down_ptr_iterator = decltype(PerPtrTopDown)::const_iterator;
211
212 top_down_ptr_iterator top_down_ptr_begin() { return PerPtrTopDown.begin(); }
213 top_down_ptr_iterator top_down_ptr_end() { return PerPtrTopDown.end(); }
214 const_top_down_ptr_iterator top_down_ptr_begin() const {
215 return PerPtrTopDown.begin();
216 }
217 const_top_down_ptr_iterator top_down_ptr_end() const {
218 return PerPtrTopDown.end();
219 }
220 bool hasTopDownPtrs() const {
221 return !PerPtrTopDown.empty();
222 }
223
224 unsigned top_down_ptr_list_size() const {
225 return std::distance(first: top_down_ptr_begin(), last: top_down_ptr_end());
226 }
227
228 using bottom_up_ptr_iterator = decltype(PerPtrBottomUp)::iterator;
229 using const_bottom_up_ptr_iterator =
230 decltype(PerPtrBottomUp)::const_iterator;
231
232 bottom_up_ptr_iterator bottom_up_ptr_begin() {
233 return PerPtrBottomUp.begin();
234 }
235 bottom_up_ptr_iterator bottom_up_ptr_end() { return PerPtrBottomUp.end(); }
236 const_bottom_up_ptr_iterator bottom_up_ptr_begin() const {
237 return PerPtrBottomUp.begin();
238 }
239 const_bottom_up_ptr_iterator bottom_up_ptr_end() const {
240 return PerPtrBottomUp.end();
241 }
242 bool hasBottomUpPtrs() const {
243 return !PerPtrBottomUp.empty();
244 }
245
246 unsigned bottom_up_ptr_list_size() const {
247 return std::distance(first: bottom_up_ptr_begin(), last: bottom_up_ptr_end());
248 }
249
250 /// Mark this block as being an entry block, which has one path from the
251 /// entry by definition.
252 void SetAsEntry() { TopDownPathCount = 1; }
253
254 /// Mark this block as being an exit block, which has one path to an exit by
255 /// definition.
256 void SetAsExit() { BottomUpPathCount = 1; }
257
258 /// Attempt to find the PtrState object describing the top down state for
259 /// pointer Arg. Return a new initialized PtrState describing the top down
260 /// state for Arg if we do not find one.
261 TopDownPtrState &getPtrTopDownState(const Value *Arg) {
262 return PerPtrTopDown[Arg];
263 }
264
265 /// Attempt to find the PtrState object describing the bottom up state for
266 /// pointer Arg. Return a new initialized PtrState describing the bottom up
267 /// state for Arg if we do not find one.
268 BottomUpPtrState &getPtrBottomUpState(const Value *Arg) {
269 return PerPtrBottomUp[Arg];
270 }
271
272 /// Attempt to find the PtrState object describing the bottom up state for
273 /// pointer Arg.
274 bottom_up_ptr_iterator findPtrBottomUpState(const Value *Arg) {
275 return PerPtrBottomUp.find(Key: Arg);
276 }
277
278 void clearBottomUpPointers() {
279 PerPtrBottomUp.clear();
280 }
281
282 void clearTopDownPointers() {
283 PerPtrTopDown.clear();
284 }
285
286 void InitFromPred(const BBState &Other);
287 void InitFromSucc(const BBState &Other);
288 void MergePred(const BBState &Other);
289 void MergeSucc(const BBState &Other);
290
291 /// Compute the number of possible unique paths from an entry to an exit
292 /// which pass through this block. This is only valid after both the
293 /// top-down and bottom-up traversals are complete.
294 ///
295 /// Returns true if overflow occurred. Returns false if overflow did not
296 /// occur.
297 bool GetAllPathCountWithOverflow(unsigned &PathCount) const {
298 if (TopDownPathCount == OverflowOccurredValue ||
299 BottomUpPathCount == OverflowOccurredValue)
300 return true;
301 unsigned long long Product =
302 (unsigned long long)TopDownPathCount*BottomUpPathCount;
303 // Overflow occurred if any of the upper bits of Product are set or if all
304 // the lower bits of Product are all set.
305 return (Product >> 32) ||
306 ((PathCount = Product) == OverflowOccurredValue);
307 }
308
309 // Specialized CFG utilities.
310 using edge_iterator = SmallVectorImpl<BasicBlock *>::const_iterator;
311
312 edge_iterator pred_begin() const { return Preds.begin(); }
313 edge_iterator pred_end() const { return Preds.end(); }
314 edge_iterator succ_begin() const { return Succs.begin(); }
315 edge_iterator succ_end() const { return Succs.end(); }
316
317 void addSucc(BasicBlock *Succ) { Succs.push_back(Elt: Succ); }
318 void addPred(BasicBlock *Pred) { Preds.push_back(Elt: Pred); }
319
320 bool isExit() const { return Succs.empty(); }
321 };
322
323} // end anonymous namespace
324
325const unsigned BBState::OverflowOccurredValue = 0xffffffff;
326
327namespace llvm {
328
329[[maybe_unused]] raw_ostream &operator<<(raw_ostream &OS, BBState &BBState);
330
331} // end namespace llvm
332
333void BBState::InitFromPred(const BBState &Other) {
334 PerPtrTopDown = Other.PerPtrTopDown;
335 TopDownPathCount = Other.TopDownPathCount;
336}
337
338void BBState::InitFromSucc(const BBState &Other) {
339 PerPtrBottomUp = Other.PerPtrBottomUp;
340 BottomUpPathCount = Other.BottomUpPathCount;
341}
342
343/// The top-down traversal uses this to merge information about predecessors to
344/// form the initial state for a new block.
345void BBState::MergePred(const BBState &Other) {
346 if (TopDownPathCount == OverflowOccurredValue)
347 return;
348
349 // Other.TopDownPathCount can be 0, in which case it is either dead or a
350 // loop backedge. Loop backedges are special.
351 TopDownPathCount += Other.TopDownPathCount;
352
353 // In order to be consistent, we clear the top down pointers when by adding
354 // TopDownPathCount becomes OverflowOccurredValue even though "true" overflow
355 // has not occurred.
356 if (TopDownPathCount == OverflowOccurredValue) {
357 clearTopDownPointers();
358 return;
359 }
360
361 // Check for overflow. If we have overflow, fall back to conservative
362 // behavior.
363 if (TopDownPathCount < Other.TopDownPathCount) {
364 TopDownPathCount = OverflowOccurredValue;
365 clearTopDownPointers();
366 return;
367 }
368
369 // For each entry in the other set, if our set has an entry with the same key,
370 // merge the entries. Otherwise, copy the entry and merge it with an empty
371 // entry.
372 for (auto MI = Other.top_down_ptr_begin(), ME = Other.top_down_ptr_end();
373 MI != ME; ++MI) {
374 auto Pair = PerPtrTopDown.insert(InsertPair: *MI);
375 Pair.first->second.Merge(Other: Pair.second ? TopDownPtrState() : MI->second,
376 /*TopDown=*/true);
377 }
378
379 // For each entry in our set, if the other set doesn't have an entry with the
380 // same key, force it to merge with an empty entry.
381 for (auto MI = top_down_ptr_begin(), ME = top_down_ptr_end(); MI != ME; ++MI)
382 if (Other.PerPtrTopDown.find(Key: MI->first) == Other.PerPtrTopDown.end())
383 MI->second.Merge(Other: TopDownPtrState(), /*TopDown=*/true);
384}
385
386/// The bottom-up traversal uses this to merge information about successors to
387/// form the initial state for a new block.
388void BBState::MergeSucc(const BBState &Other) {
389 if (BottomUpPathCount == OverflowOccurredValue)
390 return;
391
392 // Other.BottomUpPathCount can be 0, in which case it is either dead or a
393 // loop backedge. Loop backedges are special.
394 BottomUpPathCount += Other.BottomUpPathCount;
395
396 // In order to be consistent, we clear the top down pointers when by adding
397 // BottomUpPathCount becomes OverflowOccurredValue even though "true" overflow
398 // has not occurred.
399 if (BottomUpPathCount == OverflowOccurredValue) {
400 clearBottomUpPointers();
401 return;
402 }
403
404 // Check for overflow. If we have overflow, fall back to conservative
405 // behavior.
406 if (BottomUpPathCount < Other.BottomUpPathCount) {
407 BottomUpPathCount = OverflowOccurredValue;
408 clearBottomUpPointers();
409 return;
410 }
411
412 // For each entry in the other set, if our set has an entry with the
413 // same key, merge the entries. Otherwise, copy the entry and merge
414 // it with an empty entry.
415 for (auto MI = Other.bottom_up_ptr_begin(), ME = Other.bottom_up_ptr_end();
416 MI != ME; ++MI) {
417 auto Pair = PerPtrBottomUp.insert(InsertPair: *MI);
418 Pair.first->second.Merge(Other: Pair.second ? BottomUpPtrState() : MI->second,
419 /*TopDown=*/false);
420 }
421
422 // For each entry in our set, if the other set doesn't have an entry
423 // with the same key, force it to merge with an empty entry.
424 for (auto MI = bottom_up_ptr_begin(), ME = bottom_up_ptr_end(); MI != ME;
425 ++MI)
426 if (Other.PerPtrBottomUp.find(Key: MI->first) == Other.PerPtrBottomUp.end())
427 MI->second.Merge(Other: BottomUpPtrState(), /*TopDown=*/false);
428}
429
430raw_ostream &llvm::operator<<(raw_ostream &OS, BBState &BBInfo) {
431 // Dump the pointers we are tracking.
432 OS << " TopDown State:\n";
433 if (!BBInfo.hasTopDownPtrs()) {
434 LLVM_DEBUG(dbgs() << " NONE!\n");
435 } else {
436 for (auto I = BBInfo.top_down_ptr_begin(), E = BBInfo.top_down_ptr_end();
437 I != E; ++I) {
438 const PtrState &P = I->second;
439 OS << " Ptr: " << *I->first
440 << "\n KnownSafe: " << (P.IsKnownSafe()?"true":"false")
441 << "\n ImpreciseRelease: "
442 << (P.IsTrackingImpreciseReleases()?"true":"false") << "\n"
443 << " HasCFGHazards: "
444 << (P.IsCFGHazardAfflicted()?"true":"false") << "\n"
445 << " KnownPositive: "
446 << (P.HasKnownPositiveRefCount()?"true":"false") << "\n"
447 << " Seq: "
448 << P.GetSeq() << "\n";
449 }
450 }
451
452 OS << " BottomUp State:\n";
453 if (!BBInfo.hasBottomUpPtrs()) {
454 LLVM_DEBUG(dbgs() << " NONE!\n");
455 } else {
456 for (auto I = BBInfo.bottom_up_ptr_begin(), E = BBInfo.bottom_up_ptr_end();
457 I != E; ++I) {
458 const PtrState &P = I->second;
459 OS << " Ptr: " << *I->first
460 << "\n KnownSafe: " << (P.IsKnownSafe()?"true":"false")
461 << "\n ImpreciseRelease: "
462 << (P.IsTrackingImpreciseReleases()?"true":"false") << "\n"
463 << " HasCFGHazards: "
464 << (P.IsCFGHazardAfflicted()?"true":"false") << "\n"
465 << " KnownPositive: "
466 << (P.HasKnownPositiveRefCount()?"true":"false") << "\n"
467 << " Seq: "
468 << P.GetSeq() << "\n";
469 }
470 }
471
472 return OS;
473}
474
475namespace {
476
477 /// The main ARC optimization pass.
478class ObjCARCOpt {
479 bool Changed = false;
480 bool CFGChanged = false;
481 ProvenanceAnalysis PA;
482
483 /// A cache of references to runtime entry point constants.
484 ARCRuntimeEntryPoints EP;
485
486 /// A cache of MDKinds that can be passed into other functions to propagate
487 /// MDKind identifiers.
488 ARCMDKindCache MDKindCache;
489
490 BundledRetainClaimRVs *BundledInsts = nullptr;
491
492 /// A flag indicating whether the optimization that removes or moves
493 /// retain/release pairs should be performed.
494 bool DisableRetainReleasePairing = false;
495
496 /// Flags which determine whether each of the interesting runtime functions
497 /// is in fact used in the current function.
498 unsigned UsedInThisFunction;
499
500 DenseMap<BasicBlock *, ColorVector> BlockEHColors;
501
502 bool OptimizeRetainRVCall(Function &F, Instruction *RetainRV);
503 void OptimizeAutoreleaseRVCall(Function &F, Instruction *AutoreleaseRV,
504 ARCInstKind &Class);
505 void OptimizeIndividualCalls(Function &F);
506
507 /// Optimize an individual call, optionally passing the
508 /// GetArgRCIdentityRoot if it has already been computed.
509 void OptimizeIndividualCallImpl(Function &F, Instruction *Inst,
510 ARCInstKind Class, const Value *Arg);
511
512 /// Try to optimize an AutoreleaseRV with a RetainRV or UnsafeClaimRV. If the
513 /// optimization occurs, returns true to indicate that the caller should
514 /// assume the instructions are dead.
515 bool OptimizeInlinedAutoreleaseRVCall(Function &F, Instruction *Inst,
516 const Value *&Arg, ARCInstKind Class,
517 Instruction *AutoreleaseRV,
518 const Value *&AutoreleaseRVArg);
519
520 void CheckForCFGHazards(const BasicBlock *BB,
521 DenseMap<const BasicBlock *, BBState> &BBStates,
522 BBState &MyStates) const;
523 bool VisitInstructionBottomUp(Instruction *Inst, BasicBlock *BB,
524 BlotMapVector<Value *, RRInfo> &Retains,
525 BBState &MyStates);
526 bool VisitBottomUp(BasicBlock *BB,
527 DenseMap<const BasicBlock *, BBState> &BBStates,
528 BlotMapVector<Value *, RRInfo> &Retains);
529 bool VisitInstructionTopDown(
530 Instruction *Inst, DenseMap<Value *, RRInfo> &Releases, BBState &MyStates,
531 const DenseMap<const Instruction *, SmallPtrSet<const Value *, 2>>
532 &ReleaseInsertPtToRCIdentityRoots);
533 bool VisitTopDown(
534 BasicBlock *BB, DenseMap<const BasicBlock *, BBState> &BBStates,
535 DenseMap<Value *, RRInfo> &Releases,
536 const DenseMap<const Instruction *, SmallPtrSet<const Value *, 2>>
537 &ReleaseInsertPtToRCIdentityRoots);
538 bool Visit(Function &F, DenseMap<const BasicBlock *, BBState> &BBStates,
539 BlotMapVector<Value *, RRInfo> &Retains,
540 DenseMap<Value *, RRInfo> &Releases);
541
542 void MoveCalls(Value *Arg, RRInfo &RetainsToMove, RRInfo &ReleasesToMove,
543 BlotMapVector<Value *, RRInfo> &Retains,
544 DenseMap<Value *, RRInfo> &Releases,
545 SmallVectorImpl<Instruction *> &DeadInsts, Module *M);
546
547 bool PairUpRetainsAndReleases(DenseMap<const BasicBlock *, BBState> &BBStates,
548 BlotMapVector<Value *, RRInfo> &Retains,
549 DenseMap<Value *, RRInfo> &Releases, Module *M,
550 Instruction *Retain,
551 SmallVectorImpl<Instruction *> &DeadInsts,
552 RRInfo &RetainsToMove, RRInfo &ReleasesToMove,
553 Value *Arg, bool KnownSafe,
554 bool &AnyPairsCompletelyEliminated);
555
556 bool PerformCodePlacement(DenseMap<const BasicBlock *, BBState> &BBStates,
557 BlotMapVector<Value *, RRInfo> &Retains,
558 DenseMap<Value *, RRInfo> &Releases, Module *M);
559
560 void OptimizeWeakCalls(Function &F);
561
562 bool OptimizeSequences(Function &F);
563
564 void OptimizeReturns(Function &F);
565
566 void OptimizeAutoreleasePools(Function &F);
567
568 template <typename PredicateT>
569 static void cloneOpBundlesIf(CallBase *CI,
570 SmallVectorImpl<OperandBundleDef> &OpBundles,
571 PredicateT Predicate) {
572 for (unsigned I = 0, E = CI->getNumOperandBundles(); I != E; ++I) {
573 OperandBundleUse B = CI->getOperandBundleAt(Index: I);
574 if (Predicate(B))
575 OpBundles.emplace_back(Args&: B);
576 }
577 }
578
579 void addOpBundleForFunclet(BasicBlock *BB,
580 SmallVectorImpl<OperandBundleDef> &OpBundles) {
581 if (!BlockEHColors.empty()) {
582 const ColorVector &CV = BlockEHColors.find(Val: BB)->second;
583 assert(CV.size() > 0 && "Uncolored block");
584 for (BasicBlock *EHPadBB : CV)
585 if (auto *EHPad =
586 dyn_cast<FuncletPadInst>(Val: EHPadBB->getFirstNonPHIIt())) {
587 OpBundles.emplace_back(Args: "funclet", Args&: EHPad);
588 return;
589 }
590 }
591 }
592
593#ifndef NDEBUG
594 void GatherStatistics(Function &F, bool AfterOptimization = false);
595#endif
596
597 public:
598 void init(Function &F);
599 bool run(Function &F, AAResults &AA);
600 bool hasCFGChanged() const { return CFGChanged; }
601};
602} // end anonymous namespace
603
604/// Turn objc_retainAutoreleasedReturnValue into objc_retain if the operand is
605/// not a return value.
606bool
607ObjCARCOpt::OptimizeRetainRVCall(Function &F, Instruction *RetainRV) {
608 // Check for the argument being from an immediately preceding call or invoke.
609 const Value *Arg = GetArgRCIdentityRoot(Inst: RetainRV);
610 if (const Instruction *Call = dyn_cast<CallBase>(Val: Arg)) {
611 if (Call->getParent() == RetainRV->getParent()) {
612 BasicBlock::const_iterator I(Call);
613 ++I;
614 while (IsNoopInstruction(I: &*I))
615 ++I;
616 if (&*I == RetainRV)
617 return false;
618 } else if (const InvokeInst *II = dyn_cast<InvokeInst>(Val: Call)) {
619 BasicBlock *RetainRVParent = RetainRV->getParent();
620 if (II->getNormalDest() == RetainRVParent) {
621 BasicBlock::const_iterator I = RetainRVParent->begin();
622 while (IsNoopInstruction(I: &*I))
623 ++I;
624 if (&*I == RetainRV)
625 return false;
626 }
627 }
628 }
629
630 assert(!BundledInsts->contains(RetainRV) &&
631 "a bundled retainRV's argument should be a call");
632
633 // Turn it to a plain objc_retain.
634 Changed = true;
635 ++NumPeeps;
636
637 LLVM_DEBUG(dbgs() << "Transforming objc_retainAutoreleasedReturnValue => "
638 "objc_retain since the operand is not a return value.\n"
639 "Old = "
640 << *RetainRV << "\n");
641
642 Function *NewDecl = EP.get(kind: ARCRuntimeEntryPointKind::Retain);
643 cast<CallInst>(Val: RetainRV)->setCalledFunction(NewDecl);
644
645 LLVM_DEBUG(dbgs() << "New = " << *RetainRV << "\n");
646
647 return false;
648}
649
650bool ObjCARCOpt::OptimizeInlinedAutoreleaseRVCall(
651 Function &F, Instruction *Inst, const Value *&Arg, ARCInstKind Class,
652 Instruction *AutoreleaseRV, const Value *&AutoreleaseRVArg) {
653 if (BundledInsts->contains(I: Inst))
654 return false;
655
656 // Must be in the same basic block.
657 assert(Inst->getParent() == AutoreleaseRV->getParent());
658
659 // Must operate on the same root.
660 Arg = GetArgRCIdentityRoot(Inst);
661 AutoreleaseRVArg = GetArgRCIdentityRoot(Inst: AutoreleaseRV);
662 if (Arg != AutoreleaseRVArg) {
663 // If there isn't an exact match, check if we have equivalent PHIs.
664 const PHINode *PN = dyn_cast<PHINode>(Val: Arg);
665 if (!PN)
666 return false;
667
668 SmallVector<const Value *, 4> ArgUsers;
669 getEquivalentPHIs(PN: *PN, PHIList&: ArgUsers);
670 if (!llvm::is_contained(Range&: ArgUsers, Element: AutoreleaseRVArg))
671 return false;
672 }
673
674 // Okay, this is a match. Merge them.
675 ++NumPeeps;
676 LLVM_DEBUG(dbgs() << "Found inlined objc_autoreleaseReturnValue '"
677 << *AutoreleaseRV << "' paired with '" << *Inst << "'\n");
678
679 // Delete the RV pair, starting with the AutoreleaseRV.
680 AutoreleaseRV->replaceAllUsesWith(
681 V: cast<CallInst>(Val: AutoreleaseRV)->getArgOperand(i: 0));
682 Changed = true;
683 EraseInstruction(CI: AutoreleaseRV);
684 if (Class == ARCInstKind::RetainRV) {
685 // AutoreleaseRV and RetainRV cancel out. Delete the RetainRV.
686 Inst->replaceAllUsesWith(V: cast<CallInst>(Val: Inst)->getArgOperand(i: 0));
687 EraseInstruction(CI: Inst);
688 return true;
689 }
690
691 // UnsafeClaimRV is a frontend peephole for RetainRV + Release. Since the
692 // AutoreleaseRV and RetainRV cancel out, replace UnsafeClaimRV with Release.
693 assert(Class == ARCInstKind::UnsafeClaimRV);
694 Value *CallArg = cast<CallInst>(Val: Inst)->getArgOperand(i: 0);
695 CallInst *Release =
696 CallInst::Create(Func: EP.get(kind: ARCRuntimeEntryPointKind::Release), Args: CallArg, NameStr: "",
697 InsertBefore: Inst->getIterator());
698 assert(IsAlwaysTail(ARCInstKind::UnsafeClaimRV) &&
699 "Expected UnsafeClaimRV to be safe to tail call");
700 Release->setTailCall();
701 Inst->replaceAllUsesWith(V: CallArg);
702 EraseInstruction(CI: Inst);
703
704 // Run the normal optimizations on Release.
705 OptimizeIndividualCallImpl(F, Inst: Release, Class: ARCInstKind::Release, Arg);
706 return true;
707}
708
709/// Turn objc_autoreleaseReturnValue into objc_autorelease if the result is not
710/// used as a return value.
711void ObjCARCOpt::OptimizeAutoreleaseRVCall(Function &F,
712 Instruction *AutoreleaseRV,
713 ARCInstKind &Class) {
714 // Check for a return of the pointer value.
715 const Value *Ptr = GetArgRCIdentityRoot(Inst: AutoreleaseRV);
716
717 // If the argument is ConstantPointerNull or UndefValue, its other users
718 // aren't actually interesting to look at.
719 if (isa<ConstantData>(Val: Ptr))
720 return;
721
722 SmallVector<const Value *, 2> Users;
723 Users.push_back(Elt: Ptr);
724
725 // Add PHIs that are equivalent to Ptr to Users.
726 if (const PHINode *PN = dyn_cast<PHINode>(Val: Ptr))
727 getEquivalentPHIs(PN: *PN, PHIList&: Users);
728
729 do {
730 Ptr = Users.pop_back_val();
731 for (const User *U : Ptr->users()) {
732 if (isa<ReturnInst>(Val: U) || GetBasicARCInstKind(V: U) == ARCInstKind::RetainRV)
733 return;
734 if (isa<BitCastInst>(Val: U))
735 Users.push_back(Elt: U);
736 }
737 } while (!Users.empty());
738
739 Changed = true;
740 ++NumPeeps;
741
742 LLVM_DEBUG(
743 dbgs() << "Transforming objc_autoreleaseReturnValue => "
744 "objc_autorelease since its operand is not used as a return "
745 "value.\n"
746 "Old = "
747 << *AutoreleaseRV << "\n");
748
749 CallInst *AutoreleaseRVCI = cast<CallInst>(Val: AutoreleaseRV);
750 Function *NewDecl = EP.get(kind: ARCRuntimeEntryPointKind::Autorelease);
751 AutoreleaseRVCI->setCalledFunction(NewDecl);
752 AutoreleaseRVCI->setTailCall(false); // Never tail call objc_autorelease.
753 Class = ARCInstKind::Autorelease;
754
755 LLVM_DEBUG(dbgs() << "New: " << *AutoreleaseRV << "\n");
756}
757
758/// Visit each call, one at a time, and make simplifications without doing any
759/// additional analysis.
760void ObjCARCOpt::OptimizeIndividualCalls(Function &F) {
761 LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeIndividualCalls ==\n");
762 // Reset all the flags in preparation for recomputing them.
763 UsedInThisFunction = 0;
764
765 // Store any delayed AutoreleaseRV intrinsics, so they can be easily paired
766 // with RetainRV and UnsafeClaimRV.
767 Instruction *DelayedAutoreleaseRV = nullptr;
768 const Value *DelayedAutoreleaseRVArg = nullptr;
769 auto setDelayedAutoreleaseRV = [&](Instruction *AutoreleaseRV) {
770 assert(!DelayedAutoreleaseRV || !AutoreleaseRV);
771 DelayedAutoreleaseRV = AutoreleaseRV;
772 DelayedAutoreleaseRVArg = nullptr;
773 };
774 auto optimizeDelayedAutoreleaseRV = [&]() {
775 if (!DelayedAutoreleaseRV)
776 return;
777 OptimizeIndividualCallImpl(F, Inst: DelayedAutoreleaseRV,
778 Class: ARCInstKind::AutoreleaseRV,
779 Arg: DelayedAutoreleaseRVArg);
780 setDelayedAutoreleaseRV(nullptr);
781 };
782 auto shouldDelayAutoreleaseRV = [&](Instruction *NonARCInst) {
783 // Nothing to delay, but we may as well skip the logic below.
784 if (!DelayedAutoreleaseRV)
785 return true;
786
787 // If we hit the end of the basic block we're not going to find an RV-pair.
788 // Stop delaying.
789 if (NonARCInst->isTerminator())
790 return false;
791
792 // Given the frontend rules for emitting AutoreleaseRV, RetainRV, and
793 // UnsafeClaimRV, it's probably safe to skip over even opaque function calls
794 // here since OptimizeInlinedAutoreleaseRVCall will confirm that they
795 // have the same RCIdentityRoot. However, what really matters is
796 // skipping instructions or intrinsics that the inliner could leave behind;
797 // be conservative for now and don't skip over opaque calls, which could
798 // potentially include other ARC calls.
799 auto *CB = dyn_cast<CallBase>(Val: NonARCInst);
800 if (!CB)
801 return true;
802 return CB->getIntrinsicID() != Intrinsic::not_intrinsic;
803 };
804
805 // Visit all objc_* calls in F.
806 for (inst_iterator I = inst_begin(F: &F), E = inst_end(F: &F); I != E; ) {
807 Instruction *Inst = &*I++;
808
809 if (auto *CI = dyn_cast<CallInst>(Val: Inst))
810 if (objcarc::hasAttachedCallOpBundle(CB: CI)) {
811 BundledInsts->insertRVCall(InsertPt: I->getIterator(), AnnotatedCall: CI);
812 Changed = true;
813 }
814
815 ARCInstKind Class = GetBasicARCInstKind(V: Inst);
816
817 // Skip this loop if this instruction isn't itself an ARC intrinsic.
818 const Value *Arg = nullptr;
819 switch (Class) {
820 default:
821 optimizeDelayedAutoreleaseRV();
822 break;
823 case ARCInstKind::CallOrUser:
824 case ARCInstKind::User:
825 case ARCInstKind::None:
826 // This is a non-ARC instruction. If we're delaying an AutoreleaseRV,
827 // check if it's safe to skip over it; if not, optimize the AutoreleaseRV
828 // now.
829 if (!shouldDelayAutoreleaseRV(Inst))
830 optimizeDelayedAutoreleaseRV();
831 continue;
832 case ARCInstKind::AutoreleaseRV:
833 optimizeDelayedAutoreleaseRV();
834 setDelayedAutoreleaseRV(Inst);
835 continue;
836 case ARCInstKind::RetainRV:
837 case ARCInstKind::UnsafeClaimRV:
838 if (DelayedAutoreleaseRV) {
839 // We have a potential RV pair. Check if they cancel out.
840 if (OptimizeInlinedAutoreleaseRVCall(F, Inst, Arg, Class,
841 AutoreleaseRV: DelayedAutoreleaseRV,
842 AutoreleaseRVArg&: DelayedAutoreleaseRVArg)) {
843 setDelayedAutoreleaseRV(nullptr);
844 continue;
845 }
846 optimizeDelayedAutoreleaseRV();
847 }
848 break;
849 }
850
851 OptimizeIndividualCallImpl(F, Inst, Class, Arg);
852 }
853
854 // Catch the final delayed AutoreleaseRV.
855 optimizeDelayedAutoreleaseRV();
856}
857
858/// This function returns true if the value is inert. An ObjC ARC runtime call
859/// taking an inert operand can be safely deleted.
860static bool isInertARCValue(Value *V, SmallPtrSet<Value *, 1> &VisitedPhis) {
861 V = V->stripPointerCasts();
862
863 if (IsNullOrUndef(V))
864 return true;
865
866 // See if this is a global attribute annotated with an 'objc_arc_inert'.
867 if (auto *GV = dyn_cast<GlobalVariable>(Val: V))
868 if (GV->hasAttribute(Kind: "objc_arc_inert"))
869 return true;
870
871 if (auto PN = dyn_cast<PHINode>(Val: V)) {
872 // Ignore this phi if it has already been discovered.
873 if (!VisitedPhis.insert(Ptr: PN).second)
874 return true;
875 // Look through phis's operands.
876 for (Value *Opnd : PN->incoming_values())
877 if (!isInertARCValue(V: Opnd, VisitedPhis))
878 return false;
879 return true;
880 }
881
882 return false;
883}
884
885void ObjCARCOpt::OptimizeIndividualCallImpl(Function &F, Instruction *Inst,
886 ARCInstKind Class,
887 const Value *Arg) {
888 LLVM_DEBUG(dbgs() << "Visiting: Class: " << Class << "; " << *Inst << "\n");
889
890 // We can delete this call if it takes an inert value.
891 SmallPtrSet<Value *, 1> VisitedPhis;
892
893 if (BundledInsts->contains(I: Inst)) {
894 UsedInThisFunction |= 1 << unsigned(Class);
895 return;
896 }
897
898 if (IsNoopOnGlobal(Class))
899 if (isInertARCValue(V: Inst->getOperand(i: 0), VisitedPhis)) {
900 if (!Inst->getType()->isVoidTy())
901 Inst->replaceAllUsesWith(V: Inst->getOperand(i: 0));
902 Inst->eraseFromParent();
903 Changed = true;
904 return;
905 }
906
907 switch (Class) {
908 default:
909 break;
910
911 // Delete no-op casts. These function calls have special semantics, but
912 // the semantics are entirely implemented via lowering in the front-end,
913 // so by the time they reach the optimizer, they are just no-op calls
914 // which return their argument.
915 //
916 // There are gray areas here, as the ability to cast reference-counted
917 // pointers to raw void* and back allows code to break ARC assumptions,
918 // however these are currently considered to be unimportant.
919 case ARCInstKind::NoopCast:
920 Changed = true;
921 ++NumNoops;
922 LLVM_DEBUG(dbgs() << "Erasing no-op cast: " << *Inst << "\n");
923 EraseInstruction(CI: Inst);
924 return;
925
926 // If the pointer-to-weak-pointer is null, it's undefined behavior.
927 case ARCInstKind::StoreWeak:
928 case ARCInstKind::LoadWeak:
929 case ARCInstKind::LoadWeakRetained:
930 case ARCInstKind::InitWeak:
931 case ARCInstKind::DestroyWeak: {
932 CallInst *CI = cast<CallInst>(Val: Inst);
933 if (IsNullOrUndef(V: CI->getArgOperand(i: 0))) {
934 Changed = true;
935 new StoreInst(ConstantInt::getTrue(Context&: CI->getContext()),
936 PoisonValue::get(T: PointerType::getUnqual(C&: CI->getContext())),
937 CI->getIterator());
938 Value *NewValue = PoisonValue::get(T: CI->getType());
939 LLVM_DEBUG(
940 dbgs() << "A null pointer-to-weak-pointer is undefined behavior."
941 "\nOld = "
942 << *CI << "\nNew = " << *NewValue << "\n");
943 CI->replaceAllUsesWith(V: NewValue);
944 CI->eraseFromParent();
945 return;
946 }
947 break;
948 }
949 case ARCInstKind::CopyWeak:
950 case ARCInstKind::MoveWeak: {
951 CallInst *CI = cast<CallInst>(Val: Inst);
952 if (IsNullOrUndef(V: CI->getArgOperand(i: 0)) ||
953 IsNullOrUndef(V: CI->getArgOperand(i: 1))) {
954 Changed = true;
955 new StoreInst(ConstantInt::getTrue(Context&: CI->getContext()),
956 PoisonValue::get(T: PointerType::getUnqual(C&: CI->getContext())),
957 CI->getIterator());
958
959 Value *NewValue = PoisonValue::get(T: CI->getType());
960 LLVM_DEBUG(
961 dbgs() << "A null pointer-to-weak-pointer is undefined behavior."
962 "\nOld = "
963 << *CI << "\nNew = " << *NewValue << "\n");
964
965 CI->replaceAllUsesWith(V: NewValue);
966 CI->eraseFromParent();
967 return;
968 }
969 break;
970 }
971 case ARCInstKind::RetainRV:
972 if (OptimizeRetainRVCall(F, RetainRV: Inst))
973 return;
974 break;
975 case ARCInstKind::AutoreleaseRV:
976 OptimizeAutoreleaseRVCall(F, AutoreleaseRV: Inst, Class);
977 break;
978 }
979
980 // objc_autorelease(x) -> objc_release(x) if x is otherwise unused.
981 if (IsAutorelease(Class) && Inst->use_empty()) {
982 CallInst *Call = cast<CallInst>(Val: Inst);
983 const Value *Arg = Call->getArgOperand(i: 0);
984 Arg = FindSingleUseIdentifiedObject(Arg);
985 if (Arg) {
986 Changed = true;
987 ++NumAutoreleases;
988
989 // Create the declaration lazily.
990 LLVMContext &C = Inst->getContext();
991
992 Function *Decl = EP.get(kind: ARCRuntimeEntryPointKind::Release);
993 CallInst *NewCall = CallInst::Create(Func: Decl, Args: Call->getArgOperand(i: 0), NameStr: "",
994 InsertBefore: Call->getIterator());
995 NewCall->setMetadata(KindID: MDKindCache.get(ID: ARCMDKindID::ImpreciseRelease),
996 Node: MDNode::get(Context&: C, MDs: {}));
997
998 LLVM_DEBUG(dbgs() << "Replacing autorelease{,RV}(x) with objc_release(x) "
999 "since x is otherwise unused.\nOld: "
1000 << *Call << "\nNew: " << *NewCall << "\n");
1001
1002 EraseInstruction(CI: Call);
1003 Inst = NewCall;
1004 Class = ARCInstKind::Release;
1005 }
1006 }
1007
1008 // For functions which can never be passed stack arguments, add
1009 // a tail keyword.
1010 if (IsAlwaysTail(Class) && !cast<CallInst>(Val: Inst)->isNoTailCall()) {
1011 Changed = true;
1012 LLVM_DEBUG(
1013 dbgs() << "Adding tail keyword to function since it can never be "
1014 "passed stack args: "
1015 << *Inst << "\n");
1016 cast<CallInst>(Val: Inst)->setTailCall();
1017 }
1018
1019 // Ensure that functions that can never have a "tail" keyword due to the
1020 // semantics of ARC truly do not do so.
1021 if (IsNeverTail(Class)) {
1022 Changed = true;
1023 LLVM_DEBUG(dbgs() << "Removing tail keyword from function: " << *Inst
1024 << "\n");
1025 cast<CallInst>(Val: Inst)->setTailCall(false);
1026 }
1027
1028 // Set nounwind as needed.
1029 if (IsNoThrow(Class)) {
1030 Changed = true;
1031 LLVM_DEBUG(dbgs() << "Found no throw class. Setting nounwind on: " << *Inst
1032 << "\n");
1033 cast<CallInst>(Val: Inst)->setDoesNotThrow();
1034 }
1035
1036 // Note: This catches instructions unrelated to ARC.
1037 if (!IsNoopOnNull(Class)) {
1038 UsedInThisFunction |= 1 << unsigned(Class);
1039 return;
1040 }
1041
1042 // If we haven't already looked up the root, look it up now.
1043 if (!Arg)
1044 Arg = GetArgRCIdentityRoot(Inst);
1045
1046 // ARC calls with null are no-ops. Delete them.
1047 if (IsNullOrUndef(V: Arg)) {
1048 Changed = true;
1049 ++NumNoops;
1050 LLVM_DEBUG(dbgs() << "ARC calls with null are no-ops. Erasing: " << *Inst
1051 << "\n");
1052 EraseInstruction(CI: Inst);
1053 return;
1054 }
1055
1056 // Keep track of which of retain, release, autorelease, and retain_block
1057 // are actually present in this function.
1058 UsedInThisFunction |= 1 << unsigned(Class);
1059
1060 // If Arg is a PHI, and one or more incoming values to the
1061 // PHI are null, and the call is control-equivalent to the PHI, and there
1062 // are no relevant side effects between the PHI and the call, and the call
1063 // is not a release that doesn't have the clang.imprecise_release tag, the
1064 // call could be pushed up to just those paths with non-null incoming
1065 // values. For now, don't bother splitting critical edges for this.
1066 if (Class == ARCInstKind::Release &&
1067 !Inst->getMetadata(KindID: MDKindCache.get(ID: ARCMDKindID::ImpreciseRelease)))
1068 return;
1069
1070 SmallVector<std::pair<Instruction *, const Value *>, 4> Worklist;
1071 Worklist.push_back(Elt: std::make_pair(x&: Inst, y&: Arg));
1072 do {
1073 std::pair<Instruction *, const Value *> Pair = Worklist.pop_back_val();
1074 Inst = Pair.first;
1075 Arg = Pair.second;
1076
1077 const PHINode *PN = dyn_cast<PHINode>(Val: Arg);
1078 if (!PN)
1079 continue;
1080
1081 // Determine if the PHI has any null operands, or any incoming
1082 // critical edges.
1083 bool HasNull = false;
1084 bool HasCriticalEdges = false;
1085 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1086 Value *Incoming = GetRCIdentityRoot(V: PN->getIncomingValue(i));
1087 if (IsNullOrUndef(V: Incoming))
1088 HasNull = true;
1089 else if (PN->getIncomingBlock(i)->getTerminator()->getNumSuccessors() !=
1090 1) {
1091 HasCriticalEdges = true;
1092 break;
1093 }
1094 }
1095 // If we have null operands and no critical edges, optimize.
1096 if (HasCriticalEdges)
1097 continue;
1098 if (!HasNull)
1099 continue;
1100
1101 Instruction *DepInst = nullptr;
1102
1103 // Check that there is nothing that cares about the reference
1104 // count between the call and the phi.
1105 switch (Class) {
1106 case ARCInstKind::Retain:
1107 case ARCInstKind::RetainBlock:
1108 // These can always be moved up.
1109 break;
1110 case ARCInstKind::Release:
1111 // These can't be moved across things that care about the retain
1112 // count.
1113 DepInst = findSingleDependency(Flavor: NeedsPositiveRetainCount, Arg,
1114 StartBB: Inst->getParent(), StartInst: Inst, PA);
1115 break;
1116 case ARCInstKind::Autorelease:
1117 // These can't be moved across autorelease pool scope boundaries.
1118 DepInst = findSingleDependency(Flavor: AutoreleasePoolBoundary, Arg,
1119 StartBB: Inst->getParent(), StartInst: Inst, PA);
1120 break;
1121 case ARCInstKind::UnsafeClaimRV:
1122 case ARCInstKind::RetainRV:
1123 case ARCInstKind::AutoreleaseRV:
1124 // Don't move these; the RV optimization depends on the autoreleaseRV
1125 // being tail called, and the retainRV being immediately after a call
1126 // (which might still happen if we get lucky with codegen layout, but
1127 // it's not worth taking the chance).
1128 continue;
1129 default:
1130 llvm_unreachable("Invalid dependence flavor");
1131 }
1132
1133 if (DepInst != PN)
1134 continue;
1135
1136 Changed = true;
1137 ++NumPartialNoops;
1138 // Clone the call into each predecessor that has a non-null value.
1139 CallInst *CInst = cast<CallInst>(Val: Inst);
1140 Type *ParamTy = CInst->getArgOperand(i: 0)->getType();
1141 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1142 Value *Incoming = GetRCIdentityRoot(V: PN->getIncomingValue(i));
1143 if (IsNullOrUndef(V: Incoming))
1144 continue;
1145 Value *Op = PN->getIncomingValue(i);
1146 BasicBlock::iterator InsertPos =
1147 PN->getIncomingBlock(i)->back().getIterator();
1148 SmallVector<OperandBundleDef, 1> OpBundles;
1149 cloneOpBundlesIf(CI: CInst, OpBundles, Predicate: [](const OperandBundleUse &B) {
1150 return B.getTagID() != LLVMContext::OB_funclet;
1151 });
1152 addOpBundleForFunclet(BB: InsertPos->getParent(), OpBundles);
1153 CallInst *Clone = CallInst::Create(CI: CInst, Bundles: OpBundles);
1154 if (Op->getType() != ParamTy)
1155 Op = new BitCastInst(Op, ParamTy, "", InsertPos);
1156 Clone->setArgOperand(i: 0, v: Op);
1157 Clone->insertBefore(BB&: *InsertPos->getParent(), InsertPos);
1158
1159 LLVM_DEBUG(dbgs() << "Cloning " << *CInst << "\n"
1160 "And inserting clone at "
1161 << *InsertPos << "\n");
1162 Worklist.push_back(Elt: std::make_pair(x&: Clone, y&: Incoming));
1163 }
1164 // Erase the original call.
1165 LLVM_DEBUG(dbgs() << "Erasing: " << *CInst << "\n");
1166 EraseInstruction(CI: CInst);
1167 } while (!Worklist.empty());
1168}
1169
1170/// If we have a top down pointer in the S_Use state, make sure that there are
1171/// no CFG hazards by checking the states of various bottom up pointers.
1172static void CheckForUseCFGHazard(const Sequence SuccSSeq,
1173 const bool SuccSRRIKnownSafe,
1174 TopDownPtrState &S,
1175 bool &SomeSuccHasSame,
1176 bool &AllSuccsHaveSame,
1177 bool &NotAllSeqEqualButKnownSafe,
1178 bool &ShouldContinue) {
1179 switch (SuccSSeq) {
1180 case S_CanRelease: {
1181 if (!S.IsKnownSafe() && !SuccSRRIKnownSafe) {
1182 S.ClearSequenceProgress();
1183 break;
1184 }
1185 S.SetCFGHazardAfflicted(true);
1186 ShouldContinue = true;
1187 break;
1188 }
1189 case S_Use:
1190 SomeSuccHasSame = true;
1191 break;
1192 case S_Stop:
1193 case S_MovableRelease:
1194 if (!S.IsKnownSafe() && !SuccSRRIKnownSafe)
1195 AllSuccsHaveSame = false;
1196 else
1197 NotAllSeqEqualButKnownSafe = true;
1198 break;
1199 case S_Retain:
1200 llvm_unreachable("bottom-up pointer in retain state!");
1201 case S_None:
1202 llvm_unreachable("This should have been handled earlier.");
1203 }
1204}
1205
1206/// If we have a Top Down pointer in the S_CanRelease state, make sure that
1207/// there are no CFG hazards by checking the states of various bottom up
1208/// pointers.
1209static void CheckForCanReleaseCFGHazard(const Sequence SuccSSeq,
1210 const bool SuccSRRIKnownSafe,
1211 TopDownPtrState &S,
1212 bool &SomeSuccHasSame,
1213 bool &AllSuccsHaveSame,
1214 bool &NotAllSeqEqualButKnownSafe) {
1215 switch (SuccSSeq) {
1216 case S_CanRelease:
1217 SomeSuccHasSame = true;
1218 break;
1219 case S_Stop:
1220 case S_MovableRelease:
1221 case S_Use:
1222 if (!S.IsKnownSafe() && !SuccSRRIKnownSafe)
1223 AllSuccsHaveSame = false;
1224 else
1225 NotAllSeqEqualButKnownSafe = true;
1226 break;
1227 case S_Retain:
1228 llvm_unreachable("bottom-up pointer in retain state!");
1229 case S_None:
1230 llvm_unreachable("This should have been handled earlier.");
1231 }
1232}
1233
1234/// Check for critical edges, loop boundaries, irreducible control flow, or
1235/// other CFG structures where moving code across the edge would result in it
1236/// being executed more.
1237void
1238ObjCARCOpt::CheckForCFGHazards(const BasicBlock *BB,
1239 DenseMap<const BasicBlock *, BBState> &BBStates,
1240 BBState &MyStates) const {
1241 // If any top-down local-use or possible-dec has a succ which is earlier in
1242 // the sequence, forget it.
1243 for (auto I = MyStates.top_down_ptr_begin(), E = MyStates.top_down_ptr_end();
1244 I != E; ++I) {
1245 TopDownPtrState &S = I->second;
1246 const Sequence Seq = I->second.GetSeq();
1247
1248 // We only care about S_Retain, S_CanRelease, and S_Use.
1249 if (Seq == S_None)
1250 continue;
1251
1252 // Make sure that if extra top down states are added in the future that this
1253 // code is updated to handle it.
1254 assert((Seq == S_Retain || Seq == S_CanRelease || Seq == S_Use) &&
1255 "Unknown top down sequence state.");
1256
1257 const Value *Arg = I->first;
1258 bool SomeSuccHasSame = false;
1259 bool AllSuccsHaveSame = true;
1260 bool NotAllSeqEqualButKnownSafe = false;
1261
1262 for (const BasicBlock *Succ : successors(BB)) {
1263 // If VisitBottomUp has pointer information for this successor, take
1264 // what we know about it.
1265 const DenseMap<const BasicBlock *, BBState>::iterator BBI =
1266 BBStates.find(Val: Succ);
1267 assert(BBI != BBStates.end());
1268 const BottomUpPtrState &SuccS = BBI->second.getPtrBottomUpState(Arg);
1269 const Sequence SuccSSeq = SuccS.GetSeq();
1270
1271 // If bottom up, the pointer is in an S_None state, clear the sequence
1272 // progress since the sequence in the bottom up state finished
1273 // suggesting a mismatch in between retains/releases. This is true for
1274 // all three cases that we are handling here: S_Retain, S_Use, and
1275 // S_CanRelease.
1276 if (SuccSSeq == S_None) {
1277 S.ClearSequenceProgress();
1278 continue;
1279 }
1280
1281 // If we have S_Use or S_CanRelease, perform our check for cfg hazard
1282 // checks.
1283 const bool SuccSRRIKnownSafe = SuccS.IsKnownSafe();
1284
1285 // *NOTE* We do not use Seq from above here since we are allowing for
1286 // S.GetSeq() to change while we are visiting basic blocks.
1287 switch(S.GetSeq()) {
1288 case S_Use: {
1289 bool ShouldContinue = false;
1290 CheckForUseCFGHazard(SuccSSeq, SuccSRRIKnownSafe, S, SomeSuccHasSame,
1291 AllSuccsHaveSame, NotAllSeqEqualButKnownSafe,
1292 ShouldContinue);
1293 if (ShouldContinue)
1294 continue;
1295 break;
1296 }
1297 case S_CanRelease:
1298 CheckForCanReleaseCFGHazard(SuccSSeq, SuccSRRIKnownSafe, S,
1299 SomeSuccHasSame, AllSuccsHaveSame,
1300 NotAllSeqEqualButKnownSafe);
1301 break;
1302 case S_Retain:
1303 case S_None:
1304 case S_Stop:
1305 case S_MovableRelease:
1306 break;
1307 }
1308 }
1309
1310 // If the state at the other end of any of the successor edges
1311 // matches the current state, require all edges to match. This
1312 // guards against loops in the middle of a sequence.
1313 if (SomeSuccHasSame && !AllSuccsHaveSame) {
1314 S.ClearSequenceProgress();
1315 } else if (NotAllSeqEqualButKnownSafe) {
1316 // If we would have cleared the state foregoing the fact that we are known
1317 // safe, stop code motion. This is because whether or not it is safe to
1318 // remove RR pairs via KnownSafe is an orthogonal concept to whether we
1319 // are allowed to perform code motion.
1320 S.SetCFGHazardAfflicted(true);
1321 }
1322 }
1323}
1324
1325bool ObjCARCOpt::VisitInstructionBottomUp(
1326 Instruction *Inst, BasicBlock *BB, BlotMapVector<Value *, RRInfo> &Retains,
1327 BBState &MyStates) {
1328 bool NestingDetected = false;
1329 ARCInstKind Class = GetARCInstKind(V: Inst);
1330 const Value *Arg = nullptr;
1331
1332 LLVM_DEBUG(dbgs() << " Class: " << Class << "\n");
1333
1334 switch (Class) {
1335 case ARCInstKind::Release: {
1336 Arg = GetArgRCIdentityRoot(Inst);
1337
1338 BottomUpPtrState &S = MyStates.getPtrBottomUpState(Arg);
1339 NestingDetected |= S.InitBottomUp(Cache&: MDKindCache, I: Inst);
1340 break;
1341 }
1342 case ARCInstKind::RetainBlock:
1343 // In OptimizeIndividualCalls, we have strength reduced all optimizable
1344 // objc_retainBlocks to objc_retains. Thus at this point any
1345 // objc_retainBlocks that we see are not optimizable.
1346 break;
1347 case ARCInstKind::Retain:
1348 case ARCInstKind::RetainRV: {
1349 Arg = GetArgRCIdentityRoot(Inst);
1350 BottomUpPtrState &S = MyStates.getPtrBottomUpState(Arg);
1351 if (S.MatchWithRetain()) {
1352 // Don't do retain+release tracking for ARCInstKind::RetainRV, because
1353 // it's better to let it remain as the first instruction after a call.
1354 if (Class != ARCInstKind::RetainRV) {
1355 LLVM_DEBUG(dbgs() << " Matching with: " << *Inst << "\n");
1356 Retains[Inst] = S.GetRRInfo();
1357 }
1358 S.ClearSequenceProgress();
1359 }
1360 // A retain moving bottom up can be a use.
1361 break;
1362 }
1363 case ARCInstKind::AutoreleasepoolPop:
1364 // Conservatively, clear MyStates for all known pointers.
1365 MyStates.clearBottomUpPointers();
1366 return NestingDetected;
1367 case ARCInstKind::AutoreleasepoolPush:
1368 case ARCInstKind::None:
1369 // These are irrelevant.
1370 return NestingDetected;
1371 default:
1372 break;
1373 }
1374
1375 // Consider any other possible effects of this instruction on each
1376 // pointer being tracked.
1377 for (auto MI = MyStates.bottom_up_ptr_begin(),
1378 ME = MyStates.bottom_up_ptr_end();
1379 MI != ME; ++MI) {
1380 const Value *Ptr = MI->first;
1381 if (Ptr == Arg)
1382 continue; // Handled above.
1383 BottomUpPtrState &S = MI->second;
1384
1385 if (S.HandlePotentialAlterRefCount(Inst, Ptr, PA, Class))
1386 continue;
1387
1388 S.HandlePotentialUse(BB, Inst, Ptr, PA, Class);
1389 }
1390
1391 return NestingDetected;
1392}
1393
1394bool ObjCARCOpt::VisitBottomUp(BasicBlock *BB,
1395 DenseMap<const BasicBlock *, BBState> &BBStates,
1396 BlotMapVector<Value *, RRInfo> &Retains) {
1397 LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::VisitBottomUp ==\n");
1398
1399 bool NestingDetected = false;
1400 BBState &MyStates = BBStates[BB];
1401
1402 // Merge the states from each successor to compute the initial state
1403 // for the current block.
1404 BBState::edge_iterator SI(MyStates.succ_begin()),
1405 SE(MyStates.succ_end());
1406 if (SI != SE) {
1407 const BasicBlock *Succ = *SI;
1408 DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Val: Succ);
1409 assert(I != BBStates.end());
1410 MyStates.InitFromSucc(Other: I->second);
1411 ++SI;
1412 for (; SI != SE; ++SI) {
1413 Succ = *SI;
1414 I = BBStates.find(Val: Succ);
1415 assert(I != BBStates.end());
1416 MyStates.MergeSucc(Other: I->second);
1417 }
1418 }
1419
1420 LLVM_DEBUG(dbgs() << "Before:\n"
1421 << BBStates[BB] << "\n"
1422 << "Performing Dataflow:\n");
1423
1424 // Visit all the instructions, bottom-up.
1425 for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; --I) {
1426 Instruction *Inst = &*std::prev(x: I);
1427
1428 // Invoke instructions are visited as part of their successors (below).
1429 if (isa<InvokeInst>(Val: Inst))
1430 continue;
1431
1432 LLVM_DEBUG(dbgs() << " Visiting " << *Inst << "\n");
1433
1434 NestingDetected |= VisitInstructionBottomUp(Inst, BB, Retains, MyStates);
1435
1436 // Bail out if the number of pointers being tracked becomes too large so
1437 // that this pass can complete in a reasonable amount of time.
1438 if (MyStates.bottom_up_ptr_list_size() > MaxPtrStates) {
1439 DisableRetainReleasePairing = true;
1440 return false;
1441 }
1442 }
1443
1444 // If there's a predecessor with an invoke, visit the invoke as if it were
1445 // part of this block, since we can't insert code after an invoke in its own
1446 // block, and we don't want to split critical edges.
1447 for (BBState::edge_iterator PI(MyStates.pred_begin()),
1448 PE(MyStates.pred_end()); PI != PE; ++PI) {
1449 BasicBlock *Pred = *PI;
1450 if (InvokeInst *II = dyn_cast<InvokeInst>(Val: &Pred->back()))
1451 NestingDetected |= VisitInstructionBottomUp(Inst: II, BB, Retains, MyStates);
1452 }
1453
1454 LLVM_DEBUG(dbgs() << "\nFinal State:\n" << BBStates[BB] << "\n");
1455
1456 return NestingDetected;
1457}
1458
1459// Fill ReleaseInsertPtToRCIdentityRoots, which is a map from insertion points
1460// to the set of RC identity roots that would be released by the release calls
1461// moved to the insertion points.
1462static void collectReleaseInsertPts(
1463 const BlotMapVector<Value *, RRInfo> &Retains,
1464 DenseMap<const Instruction *, SmallPtrSet<const Value *, 2>>
1465 &ReleaseInsertPtToRCIdentityRoots) {
1466 for (const auto &P : Retains) {
1467 // Retains is a map from an objc_retain call to a RRInfo of the RC identity
1468 // root of the call. Get the RC identity root of the objc_retain call.
1469 Instruction *Retain = cast<Instruction>(Val: P.first);
1470 Value *Root = GetRCIdentityRoot(V: Retain->getOperand(i: 0));
1471 // Collect all the insertion points of the objc_release calls that release
1472 // the RC identity root of the objc_retain call.
1473 for (const Instruction *InsertPt : P.second.ReverseInsertPts)
1474 ReleaseInsertPtToRCIdentityRoots[InsertPt].insert(Ptr: Root);
1475 }
1476}
1477
1478// Get the RC identity roots from an insertion point of an objc_release call.
1479// Return nullptr if the passed instruction isn't an insertion point.
1480static const SmallPtrSet<const Value *, 2> *
1481getRCIdentityRootsFromReleaseInsertPt(
1482 const Instruction *InsertPt,
1483 const DenseMap<const Instruction *, SmallPtrSet<const Value *, 2>>
1484 &ReleaseInsertPtToRCIdentityRoots) {
1485 auto I = ReleaseInsertPtToRCIdentityRoots.find(Val: InsertPt);
1486 if (I == ReleaseInsertPtToRCIdentityRoots.end())
1487 return nullptr;
1488 return &I->second;
1489}
1490
1491bool ObjCARCOpt::VisitInstructionTopDown(
1492 Instruction *Inst, DenseMap<Value *, RRInfo> &Releases, BBState &MyStates,
1493 const DenseMap<const Instruction *, SmallPtrSet<const Value *, 2>>
1494 &ReleaseInsertPtToRCIdentityRoots) {
1495 bool NestingDetected = false;
1496 ARCInstKind Class = GetARCInstKind(V: Inst);
1497 const Value *Arg = nullptr;
1498
1499 // Make sure a call to objc_retain isn't moved past insertion points of calls
1500 // to objc_release.
1501 if (const SmallPtrSet<const Value *, 2> *Roots =
1502 getRCIdentityRootsFromReleaseInsertPt(
1503 InsertPt: Inst, ReleaseInsertPtToRCIdentityRoots))
1504 for (const auto *Root : *Roots) {
1505 TopDownPtrState &S = MyStates.getPtrTopDownState(Arg: Root);
1506 // Disable code motion if the current position is S_Retain to prevent
1507 // moving the objc_retain call past objc_release calls. If it's
1508 // S_CanRelease or larger, it's not necessary to disable code motion as
1509 // the insertion points that prevent the objc_retain call from moving down
1510 // should have been set already.
1511 if (S.GetSeq() == S_Retain)
1512 S.SetCFGHazardAfflicted(true);
1513 }
1514
1515 LLVM_DEBUG(dbgs() << " Class: " << Class << "\n");
1516
1517 switch (Class) {
1518 case ARCInstKind::RetainBlock:
1519 // In OptimizeIndividualCalls, we have strength reduced all optimizable
1520 // objc_retainBlocks to objc_retains. Thus at this point any
1521 // objc_retainBlocks that we see are not optimizable. We need to break since
1522 // a retain can be a potential use.
1523 break;
1524 case ARCInstKind::Retain:
1525 case ARCInstKind::RetainRV: {
1526 Arg = GetArgRCIdentityRoot(Inst);
1527 TopDownPtrState &S = MyStates.getPtrTopDownState(Arg);
1528 NestingDetected |= S.InitTopDown(Kind: Class, I: Inst);
1529 // A retain can be a potential use; proceed to the generic checking
1530 // code below.
1531 break;
1532 }
1533 case ARCInstKind::Release: {
1534 Arg = GetArgRCIdentityRoot(Inst);
1535 TopDownPtrState &S = MyStates.getPtrTopDownState(Arg);
1536 // Try to form a tentative pair in between this release instruction and the
1537 // top down pointers that we are tracking.
1538 if (S.MatchWithRelease(Cache&: MDKindCache, Release: Inst)) {
1539 // If we succeed, copy S's RRInfo into the Release -> {Retain Set
1540 // Map}. Then we clear S.
1541 LLVM_DEBUG(dbgs() << " Matching with: " << *Inst << "\n");
1542 Releases[Inst] = S.GetRRInfo();
1543 S.ClearSequenceProgress();
1544 }
1545 break;
1546 }
1547 case ARCInstKind::AutoreleasepoolPop:
1548 // Conservatively, clear MyStates for all known pointers.
1549 MyStates.clearTopDownPointers();
1550 return false;
1551 case ARCInstKind::AutoreleasepoolPush:
1552 case ARCInstKind::None:
1553 // These can not be uses of
1554 return false;
1555 default:
1556 break;
1557 }
1558
1559 // Consider any other possible effects of this instruction on each
1560 // pointer being tracked.
1561 for (auto MI = MyStates.top_down_ptr_begin(),
1562 ME = MyStates.top_down_ptr_end();
1563 MI != ME; ++MI) {
1564 const Value *Ptr = MI->first;
1565 if (Ptr == Arg)
1566 continue; // Handled above.
1567 TopDownPtrState &S = MI->second;
1568 if (S.HandlePotentialAlterRefCount(Inst, Ptr, PA, Class, BundledRVs: *BundledInsts))
1569 continue;
1570
1571 S.HandlePotentialUse(Inst, Ptr, PA, Class);
1572 }
1573
1574 return NestingDetected;
1575}
1576
1577bool ObjCARCOpt::VisitTopDown(
1578 BasicBlock *BB, DenseMap<const BasicBlock *, BBState> &BBStates,
1579 DenseMap<Value *, RRInfo> &Releases,
1580 const DenseMap<const Instruction *, SmallPtrSet<const Value *, 2>>
1581 &ReleaseInsertPtToRCIdentityRoots) {
1582 LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::VisitTopDown ==\n");
1583 bool NestingDetected = false;
1584 BBState &MyStates = BBStates[BB];
1585
1586 // Merge the states from each predecessor to compute the initial state
1587 // for the current block.
1588 BBState::edge_iterator PI(MyStates.pred_begin()),
1589 PE(MyStates.pred_end());
1590 if (PI != PE) {
1591 const BasicBlock *Pred = *PI;
1592 DenseMap<const BasicBlock *, BBState>::iterator I = BBStates.find(Val: Pred);
1593 assert(I != BBStates.end());
1594 MyStates.InitFromPred(Other: I->second);
1595 ++PI;
1596 for (; PI != PE; ++PI) {
1597 Pred = *PI;
1598 I = BBStates.find(Val: Pred);
1599 assert(I != BBStates.end());
1600 MyStates.MergePred(Other: I->second);
1601 }
1602 }
1603
1604 // Check that BB and MyStates have the same number of predecessors. This
1605 // prevents retain calls that live outside a loop from being moved into the
1606 // loop.
1607 if (!BB->hasNPredecessors(N: MyStates.pred_end() - MyStates.pred_begin()))
1608 for (auto I = MyStates.top_down_ptr_begin(),
1609 E = MyStates.top_down_ptr_end();
1610 I != E; ++I)
1611 I->second.SetCFGHazardAfflicted(true);
1612
1613 LLVM_DEBUG(dbgs() << "Before:\n"
1614 << BBStates[BB] << "\n"
1615 << "Performing Dataflow:\n");
1616
1617 // Visit all the instructions, top-down.
1618 for (Instruction &Inst : *BB) {
1619 LLVM_DEBUG(dbgs() << " Visiting " << Inst << "\n");
1620
1621 NestingDetected |= VisitInstructionTopDown(
1622 Inst: &Inst, Releases, MyStates, ReleaseInsertPtToRCIdentityRoots);
1623
1624 // Bail out if the number of pointers being tracked becomes too large so
1625 // that this pass can complete in a reasonable amount of time.
1626 if (MyStates.top_down_ptr_list_size() > MaxPtrStates) {
1627 DisableRetainReleasePairing = true;
1628 return false;
1629 }
1630 }
1631
1632 LLVM_DEBUG(dbgs() << "\nState Before Checking for CFG Hazards:\n"
1633 << BBStates[BB] << "\n\n");
1634 CheckForCFGHazards(BB, BBStates, MyStates);
1635 LLVM_DEBUG(dbgs() << "Final State:\n" << BBStates[BB] << "\n");
1636 return NestingDetected;
1637}
1638
1639static void
1640ComputePostOrders(Function &F,
1641 SmallVectorImpl<BasicBlock *> &PostOrder,
1642 SmallVectorImpl<BasicBlock *> &ReverseCFGPostOrder,
1643 unsigned NoObjCARCExceptionsMDKind,
1644 DenseMap<const BasicBlock *, BBState> &BBStates) {
1645 /// The visited set, for doing DFS walks.
1646 SmallPtrSet<BasicBlock *, 16> Visited;
1647
1648 // Do DFS, computing the PostOrder.
1649 SmallPtrSet<BasicBlock *, 16> OnStack;
1650 SmallVector<std::pair<BasicBlock *, succ_iterator>, 16> SuccStack;
1651
1652 // Functions always have exactly one entry block, and we don't have
1653 // any other block that we treat like an entry block.
1654 BasicBlock *EntryBB = &F.getEntryBlock();
1655 BBState &MyStates = BBStates[EntryBB];
1656 MyStates.SetAsEntry();
1657 Instruction *EntryTI = EntryBB->getTerminator();
1658 SuccStack.push_back(Elt: std::make_pair(x&: EntryBB, y: succ_iterator(EntryTI)));
1659 Visited.insert(Ptr: EntryBB);
1660 OnStack.insert(Ptr: EntryBB);
1661 do {
1662 dfs_next_succ:
1663 BasicBlock *CurrBB = SuccStack.back().first;
1664 succ_iterator SE(CurrBB->getTerminator(), false);
1665
1666 while (SuccStack.back().second != SE) {
1667 BasicBlock *SuccBB = *SuccStack.back().second++;
1668 if (Visited.insert(Ptr: SuccBB).second) {
1669 SuccStack.push_back(
1670 Elt: std::make_pair(x&: SuccBB, y: succ_iterator(SuccBB->getTerminator())));
1671 BBStates[CurrBB].addSucc(Succ: SuccBB);
1672 BBState &SuccStates = BBStates[SuccBB];
1673 SuccStates.addPred(Pred: CurrBB);
1674 OnStack.insert(Ptr: SuccBB);
1675 goto dfs_next_succ;
1676 }
1677
1678 if (!OnStack.count(Ptr: SuccBB)) {
1679 BBStates[CurrBB].addSucc(Succ: SuccBB);
1680 BBStates[SuccBB].addPred(Pred: CurrBB);
1681 }
1682 }
1683 OnStack.erase(Ptr: CurrBB);
1684 PostOrder.push_back(Elt: CurrBB);
1685 SuccStack.pop_back();
1686 } while (!SuccStack.empty());
1687
1688 Visited.clear();
1689
1690 // Do reverse-CFG DFS, computing the reverse-CFG PostOrder.
1691 // Functions may have many exits, and there also blocks which we treat
1692 // as exits due to ignored edges.
1693 SmallVector<std::pair<BasicBlock *, BBState::edge_iterator>, 16> PredStack;
1694 for (BasicBlock &ExitBB : F) {
1695 BBState &MyStates = BBStates[&ExitBB];
1696 if (!MyStates.isExit())
1697 continue;
1698
1699 MyStates.SetAsExit();
1700
1701 PredStack.push_back(Elt: std::make_pair(x: &ExitBB, y: MyStates.pred_begin()));
1702 Visited.insert(Ptr: &ExitBB);
1703 while (!PredStack.empty()) {
1704 reverse_dfs_next_succ:
1705 BBState::edge_iterator PE = BBStates[PredStack.back().first].pred_end();
1706 while (PredStack.back().second != PE) {
1707 BasicBlock *BB = *PredStack.back().second++;
1708 if (Visited.insert(Ptr: BB).second) {
1709 PredStack.push_back(Elt: std::make_pair(x&: BB, y: BBStates[BB].pred_begin()));
1710 goto reverse_dfs_next_succ;
1711 }
1712 }
1713 ReverseCFGPostOrder.push_back(Elt: PredStack.pop_back_val().first);
1714 }
1715 }
1716}
1717
1718// Visit the function both top-down and bottom-up.
1719bool ObjCARCOpt::Visit(Function &F,
1720 DenseMap<const BasicBlock *, BBState> &BBStates,
1721 BlotMapVector<Value *, RRInfo> &Retains,
1722 DenseMap<Value *, RRInfo> &Releases) {
1723 // Use reverse-postorder traversals, because we magically know that loops
1724 // will be well behaved, i.e. they won't repeatedly call retain on a single
1725 // pointer without doing a release. We can't use the ReversePostOrderTraversal
1726 // class here because we want the reverse-CFG postorder to consider each
1727 // function exit point, and we want to ignore selected cycle edges.
1728 SmallVector<BasicBlock *, 16> PostOrder;
1729 SmallVector<BasicBlock *, 16> ReverseCFGPostOrder;
1730 ComputePostOrders(F, PostOrder, ReverseCFGPostOrder,
1731 NoObjCARCExceptionsMDKind: MDKindCache.get(ID: ARCMDKindID::NoObjCARCExceptions),
1732 BBStates);
1733
1734 // Use reverse-postorder on the reverse CFG for bottom-up.
1735 bool BottomUpNestingDetected = false;
1736 for (BasicBlock *BB : llvm::reverse(C&: ReverseCFGPostOrder)) {
1737 BottomUpNestingDetected |= VisitBottomUp(BB, BBStates, Retains);
1738 if (DisableRetainReleasePairing)
1739 return false;
1740 }
1741
1742 DenseMap<const Instruction *, SmallPtrSet<const Value *, 2>>
1743 ReleaseInsertPtToRCIdentityRoots;
1744 collectReleaseInsertPts(Retains, ReleaseInsertPtToRCIdentityRoots);
1745
1746 // Use reverse-postorder for top-down.
1747 bool TopDownNestingDetected = false;
1748 for (BasicBlock *BB : llvm::reverse(C&: PostOrder)) {
1749 TopDownNestingDetected |=
1750 VisitTopDown(BB, BBStates, Releases, ReleaseInsertPtToRCIdentityRoots);
1751 if (DisableRetainReleasePairing)
1752 return false;
1753 }
1754
1755 return TopDownNestingDetected && BottomUpNestingDetected;
1756}
1757
1758/// Move the calls in RetainsToMove and ReleasesToMove.
1759void ObjCARCOpt::MoveCalls(Value *Arg, RRInfo &RetainsToMove,
1760 RRInfo &ReleasesToMove,
1761 BlotMapVector<Value *, RRInfo> &Retains,
1762 DenseMap<Value *, RRInfo> &Releases,
1763 SmallVectorImpl<Instruction *> &DeadInsts,
1764 Module *M) {
1765 LLVM_DEBUG(dbgs() << "== ObjCARCOpt::MoveCalls ==\n");
1766
1767 // Insert the new retain and release calls.
1768 for (Instruction *InsertPt : ReleasesToMove.ReverseInsertPts) {
1769 Function *Decl = EP.get(kind: ARCRuntimeEntryPointKind::Retain);
1770 SmallVector<OperandBundleDef, 1> BundleList;
1771 addOpBundleForFunclet(BB: InsertPt->getParent(), OpBundles&: BundleList);
1772 CallInst *Call =
1773 CallInst::Create(Func: Decl, Args: Arg, Bundles: BundleList, NameStr: "", InsertBefore: InsertPt->getIterator());
1774 Call->setDoesNotThrow();
1775 Call->setTailCall();
1776
1777 LLVM_DEBUG(dbgs() << "Inserting new Retain: " << *Call
1778 << "\n"
1779 "At insertion point: "
1780 << *InsertPt << "\n");
1781 }
1782 for (Instruction *InsertPt : RetainsToMove.ReverseInsertPts) {
1783 Function *Decl = EP.get(kind: ARCRuntimeEntryPointKind::Release);
1784 SmallVector<OperandBundleDef, 1> BundleList;
1785 addOpBundleForFunclet(BB: InsertPt->getParent(), OpBundles&: BundleList);
1786 CallInst *Call =
1787 CallInst::Create(Func: Decl, Args: Arg, Bundles: BundleList, NameStr: "", InsertBefore: InsertPt->getIterator());
1788 // Attach a clang.imprecise_release metadata tag, if appropriate.
1789 if (MDNode *M = ReleasesToMove.ReleaseMetadata)
1790 Call->setMetadata(KindID: MDKindCache.get(ID: ARCMDKindID::ImpreciseRelease), Node: M);
1791 Call->setDoesNotThrow();
1792 if (ReleasesToMove.IsTailCallRelease)
1793 Call->setTailCall();
1794
1795 LLVM_DEBUG(dbgs() << "Inserting new Release: " << *Call
1796 << "\n"
1797 "At insertion point: "
1798 << *InsertPt << "\n");
1799 }
1800
1801 // Delete the original retain and release calls.
1802 for (Instruction *OrigRetain : RetainsToMove.Calls) {
1803 Retains.blot(Key: OrigRetain);
1804 DeadInsts.push_back(Elt: OrigRetain);
1805 LLVM_DEBUG(dbgs() << "Deleting retain: " << *OrigRetain << "\n");
1806 }
1807 for (Instruction *OrigRelease : ReleasesToMove.Calls) {
1808 Releases.erase(Val: OrigRelease);
1809 DeadInsts.push_back(Elt: OrigRelease);
1810 LLVM_DEBUG(dbgs() << "Deleting release: " << *OrigRelease << "\n");
1811 }
1812}
1813
1814bool ObjCARCOpt::PairUpRetainsAndReleases(
1815 DenseMap<const BasicBlock *, BBState> &BBStates,
1816 BlotMapVector<Value *, RRInfo> &Retains,
1817 DenseMap<Value *, RRInfo> &Releases, Module *M,
1818 Instruction *Retain,
1819 SmallVectorImpl<Instruction *> &DeadInsts, RRInfo &RetainsToMove,
1820 RRInfo &ReleasesToMove, Value *Arg, bool KnownSafe,
1821 bool &AnyPairsCompletelyEliminated) {
1822 // If a pair happens in a region where it is known that the reference count
1823 // is already incremented, we can similarly ignore possible decrements unless
1824 // we are dealing with a retainable object with multiple provenance sources.
1825 bool KnownSafeTD = true, KnownSafeBU = true;
1826 bool CFGHazardAfflicted = false;
1827
1828 // Connect the dots between the top-down-collected RetainsToMove and
1829 // bottom-up-collected ReleasesToMove to form sets of related calls.
1830 // This is an iterative process so that we connect multiple releases
1831 // to multiple retains if needed.
1832 unsigned OldDelta = 0;
1833 unsigned NewDelta = 0;
1834 unsigned OldCount = 0;
1835 unsigned NewCount = 0;
1836 bool FirstRelease = true;
1837 for (SmallVector<Instruction *, 4> NewRetains{Retain};;) {
1838 SmallVector<Instruction *, 4> NewReleases;
1839 for (Instruction *NewRetain : NewRetains) {
1840 auto It = Retains.find(Key: NewRetain);
1841 assert(It != Retains.end());
1842 const RRInfo &NewRetainRRI = It->second;
1843 KnownSafeTD &= NewRetainRRI.KnownSafe;
1844 CFGHazardAfflicted |= NewRetainRRI.CFGHazardAfflicted;
1845 for (Instruction *NewRetainRelease : NewRetainRRI.Calls) {
1846 auto Jt = Releases.find(Val: NewRetainRelease);
1847 if (Jt == Releases.end())
1848 return false;
1849 const RRInfo &NewRetainReleaseRRI = Jt->second;
1850
1851 // If the release does not have a reference to the retain as well,
1852 // something happened which is unaccounted for. Do not do anything.
1853 //
1854 // This can happen if we catch an additive overflow during path count
1855 // merging.
1856 if (!NewRetainReleaseRRI.Calls.count(Ptr: NewRetain))
1857 return false;
1858
1859 if (ReleasesToMove.Calls.insert(Ptr: NewRetainRelease).second) {
1860 // If we overflow when we compute the path count, don't remove/move
1861 // anything.
1862 const BBState &NRRBBState = BBStates[NewRetainRelease->getParent()];
1863 unsigned PathCount = BBState::OverflowOccurredValue;
1864 if (NRRBBState.GetAllPathCountWithOverflow(PathCount))
1865 return false;
1866 assert(PathCount != BBState::OverflowOccurredValue &&
1867 "PathCount at this point can not be "
1868 "OverflowOccurredValue.");
1869 OldDelta -= PathCount;
1870
1871 // Merge the ReleaseMetadata and IsTailCallRelease values.
1872 if (FirstRelease) {
1873 ReleasesToMove.ReleaseMetadata =
1874 NewRetainReleaseRRI.ReleaseMetadata;
1875 ReleasesToMove.IsTailCallRelease =
1876 NewRetainReleaseRRI.IsTailCallRelease;
1877 FirstRelease = false;
1878 } else {
1879 if (ReleasesToMove.ReleaseMetadata !=
1880 NewRetainReleaseRRI.ReleaseMetadata)
1881 ReleasesToMove.ReleaseMetadata = nullptr;
1882 if (ReleasesToMove.IsTailCallRelease !=
1883 NewRetainReleaseRRI.IsTailCallRelease)
1884 ReleasesToMove.IsTailCallRelease = false;
1885 }
1886
1887 // Collect the optimal insertion points.
1888 if (!KnownSafe)
1889 for (Instruction *RIP : NewRetainReleaseRRI.ReverseInsertPts) {
1890 if (ReleasesToMove.ReverseInsertPts.insert(Ptr: RIP).second) {
1891 // If we overflow when we compute the path count, don't
1892 // remove/move anything.
1893 const BBState &RIPBBState = BBStates[RIP->getParent()];
1894 PathCount = BBState::OverflowOccurredValue;
1895 if (RIPBBState.GetAllPathCountWithOverflow(PathCount))
1896 return false;
1897 assert(PathCount != BBState::OverflowOccurredValue &&
1898 "PathCount at this point can not be "
1899 "OverflowOccurredValue.");
1900 NewDelta -= PathCount;
1901 }
1902 }
1903 NewReleases.push_back(Elt: NewRetainRelease);
1904 }
1905 }
1906 }
1907 NewRetains.clear();
1908 if (NewReleases.empty()) break;
1909
1910 // Back the other way.
1911 for (Instruction *NewRelease : NewReleases) {
1912 auto It = Releases.find(Val: NewRelease);
1913 assert(It != Releases.end());
1914 const RRInfo &NewReleaseRRI = It->second;
1915 KnownSafeBU &= NewReleaseRRI.KnownSafe;
1916 CFGHazardAfflicted |= NewReleaseRRI.CFGHazardAfflicted;
1917 for (Instruction *NewReleaseRetain : NewReleaseRRI.Calls) {
1918 auto Jt = Retains.find(Key: NewReleaseRetain);
1919 if (Jt == Retains.end())
1920 return false;
1921 const RRInfo &NewReleaseRetainRRI = Jt->second;
1922
1923 // If the retain does not have a reference to the release as well,
1924 // something happened which is unaccounted for. Do not do anything.
1925 //
1926 // This can happen if we catch an additive overflow during path count
1927 // merging.
1928 if (!NewReleaseRetainRRI.Calls.count(Ptr: NewRelease))
1929 return false;
1930
1931 if (RetainsToMove.Calls.insert(Ptr: NewReleaseRetain).second) {
1932 // If we overflow when we compute the path count, don't remove/move
1933 // anything.
1934 const BBState &NRRBBState = BBStates[NewReleaseRetain->getParent()];
1935 unsigned PathCount = BBState::OverflowOccurredValue;
1936 if (NRRBBState.GetAllPathCountWithOverflow(PathCount))
1937 return false;
1938 assert(PathCount != BBState::OverflowOccurredValue &&
1939 "PathCount at this point can not be "
1940 "OverflowOccurredValue.");
1941 OldDelta += PathCount;
1942 OldCount += PathCount;
1943
1944 // Collect the optimal insertion points.
1945 if (!KnownSafe)
1946 for (Instruction *RIP : NewReleaseRetainRRI.ReverseInsertPts) {
1947 if (RetainsToMove.ReverseInsertPts.insert(Ptr: RIP).second) {
1948 // If we overflow when we compute the path count, don't
1949 // remove/move anything.
1950 const BBState &RIPBBState = BBStates[RIP->getParent()];
1951
1952 PathCount = BBState::OverflowOccurredValue;
1953 if (RIPBBState.GetAllPathCountWithOverflow(PathCount))
1954 return false;
1955 assert(PathCount != BBState::OverflowOccurredValue &&
1956 "PathCount at this point can not be "
1957 "OverflowOccurredValue.");
1958 NewDelta += PathCount;
1959 NewCount += PathCount;
1960 }
1961 }
1962 NewRetains.push_back(Elt: NewReleaseRetain);
1963 }
1964 }
1965 }
1966 if (NewRetains.empty()) break;
1967 }
1968
1969 // We can only remove pointers if we are known safe in both directions.
1970 bool UnconditionallySafe = KnownSafeTD && KnownSafeBU;
1971 if (UnconditionallySafe) {
1972 RetainsToMove.ReverseInsertPts.clear();
1973 ReleasesToMove.ReverseInsertPts.clear();
1974 NewCount = 0;
1975 } else {
1976 // Determine whether the new insertion points we computed preserve the
1977 // balance of retain and release calls through the program.
1978 // TODO: If the fully aggressive solution isn't valid, try to find a
1979 // less aggressive solution which is.
1980 if (NewDelta != 0)
1981 return false;
1982
1983 // At this point, we are not going to remove any RR pairs, but we still are
1984 // able to move RR pairs. If one of our pointers is afflicted with
1985 // CFGHazards, we cannot perform such code motion so exit early.
1986 const bool WillPerformCodeMotion =
1987 !RetainsToMove.ReverseInsertPts.empty() ||
1988 !ReleasesToMove.ReverseInsertPts.empty();
1989 if (CFGHazardAfflicted && WillPerformCodeMotion)
1990 return false;
1991 }
1992
1993 // Determine whether the original call points are balanced in the retain and
1994 // release calls through the program. If not, conservatively don't touch
1995 // them.
1996 // TODO: It's theoretically possible to do code motion in this case, as
1997 // long as the existing imbalances are maintained.
1998 if (OldDelta != 0)
1999 return false;
2000
2001 Changed = true;
2002 assert(OldCount != 0 && "Unreachable code?");
2003 NumRRs += OldCount - NewCount;
2004 // Set to true if we completely removed any RR pairs.
2005 AnyPairsCompletelyEliminated = NewCount == 0;
2006
2007 // We can move calls!
2008 return true;
2009}
2010
2011/// Identify pairings between the retains and releases, and delete and/or move
2012/// them.
2013bool ObjCARCOpt::PerformCodePlacement(
2014 DenseMap<const BasicBlock *, BBState> &BBStates,
2015 BlotMapVector<Value *, RRInfo> &Retains,
2016 DenseMap<Value *, RRInfo> &Releases, Module *M) {
2017 LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::PerformCodePlacement ==\n");
2018
2019 bool AnyPairsCompletelyEliminated = false;
2020 SmallVector<Instruction *, 8> DeadInsts;
2021
2022 // Visit each retain.
2023 for (BlotMapVector<Value *, RRInfo>::const_iterator I = Retains.begin(),
2024 E = Retains.end();
2025 I != E; ++I) {
2026 Value *V = I->first;
2027 if (!V) continue; // blotted
2028
2029 Instruction *Retain = cast<Instruction>(Val: V);
2030
2031 LLVM_DEBUG(dbgs() << "Visiting: " << *Retain << "\n");
2032
2033 Value *Arg = GetArgRCIdentityRoot(Inst: Retain);
2034
2035 // If the object being released is in static or stack storage, we know it's
2036 // not being managed by ObjC reference counting, so we can delete pairs
2037 // regardless of what possible decrements or uses lie between them.
2038 bool KnownSafe = isa<Constant>(Val: Arg) || isa<AllocaInst>(Val: Arg);
2039
2040 // A constant pointer can't be pointing to an object on the heap. It may
2041 // be reference-counted, but it won't be deleted.
2042 if (const LoadInst *LI = dyn_cast<LoadInst>(Val: Arg))
2043 if (const GlobalVariable *GV =
2044 dyn_cast<GlobalVariable>(
2045 Val: GetRCIdentityRoot(V: LI->getPointerOperand())))
2046 if (GV->isConstant())
2047 KnownSafe = true;
2048
2049 // Connect the dots between the top-down-collected RetainsToMove and
2050 // bottom-up-collected ReleasesToMove to form sets of related calls.
2051 RRInfo RetainsToMove, ReleasesToMove;
2052
2053 bool PerformMoveCalls = PairUpRetainsAndReleases(
2054 BBStates, Retains, Releases, M, Retain, DeadInsts,
2055 RetainsToMove, ReleasesToMove, Arg, KnownSafe,
2056 AnyPairsCompletelyEliminated);
2057
2058 if (PerformMoveCalls) {
2059 // Ok, everything checks out and we're all set. Let's move/delete some
2060 // code!
2061 MoveCalls(Arg, RetainsToMove, ReleasesToMove,
2062 Retains, Releases, DeadInsts, M);
2063 }
2064 }
2065
2066 // Now that we're done moving everything, we can delete the newly dead
2067 // instructions, as we no longer need them as insert points.
2068 while (!DeadInsts.empty())
2069 EraseInstruction(CI: DeadInsts.pop_back_val());
2070
2071 return AnyPairsCompletelyEliminated;
2072}
2073
2074/// Weak pointer optimizations.
2075void ObjCARCOpt::OptimizeWeakCalls(Function &F) {
2076 LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeWeakCalls ==\n");
2077
2078 // First, do memdep-style RLE and S2L optimizations. We can't use memdep
2079 // itself because it uses AliasAnalysis and we need to do provenance
2080 // queries instead.
2081 for (inst_iterator I = inst_begin(F: &F), E = inst_end(F: &F); I != E; ) {
2082 Instruction *Inst = &*I++;
2083
2084 LLVM_DEBUG(dbgs() << "Visiting: " << *Inst << "\n");
2085
2086 ARCInstKind Class = GetBasicARCInstKind(V: Inst);
2087 if (Class != ARCInstKind::LoadWeak &&
2088 Class != ARCInstKind::LoadWeakRetained)
2089 continue;
2090
2091 // Delete objc_loadWeak calls with no users.
2092 if (Class == ARCInstKind::LoadWeak && Inst->use_empty()) {
2093 Inst->eraseFromParent();
2094 Changed = true;
2095 continue;
2096 }
2097
2098 // TODO: For now, just look for an earlier available version of this value
2099 // within the same block. Theoretically, we could do memdep-style non-local
2100 // analysis too, but that would want caching. A better approach would be to
2101 // use the technique that EarlyCSE uses.
2102 inst_iterator Current = std::prev(x: I);
2103 BasicBlock *CurrentBB = &*Current.getBasicBlockIterator();
2104 for (BasicBlock::iterator B = CurrentBB->begin(),
2105 J = Current.getInstructionIterator();
2106 J != B; --J) {
2107 Instruction *EarlierInst = &*std::prev(x: J);
2108 ARCInstKind EarlierClass = GetARCInstKind(V: EarlierInst);
2109 switch (EarlierClass) {
2110 case ARCInstKind::LoadWeak:
2111 case ARCInstKind::LoadWeakRetained: {
2112 // If this is loading from the same pointer, replace this load's value
2113 // with that one.
2114 CallInst *Call = cast<CallInst>(Val: Inst);
2115 CallInst *EarlierCall = cast<CallInst>(Val: EarlierInst);
2116 Value *Arg = Call->getArgOperand(i: 0);
2117 Value *EarlierArg = EarlierCall->getArgOperand(i: 0);
2118 switch (PA.getAA()->alias(V1: Arg, V2: EarlierArg)) {
2119 case AliasResult::MustAlias:
2120 Changed = true;
2121 // If the load has a builtin retain, insert a plain retain for it.
2122 if (Class == ARCInstKind::LoadWeakRetained) {
2123 Function *Decl = EP.get(kind: ARCRuntimeEntryPointKind::Retain);
2124 CallInst *CI =
2125 CallInst::Create(Func: Decl, Args: EarlierCall, NameStr: "", InsertBefore: Call->getIterator());
2126 CI->setTailCall();
2127 }
2128 // Zap the fully redundant load.
2129 Call->replaceAllUsesWith(V: EarlierCall);
2130 Call->eraseFromParent();
2131 goto clobbered;
2132 case AliasResult::MayAlias:
2133 case AliasResult::PartialAlias:
2134 goto clobbered;
2135 case AliasResult::NoAlias:
2136 break;
2137 }
2138 break;
2139 }
2140 case ARCInstKind::StoreWeak:
2141 case ARCInstKind::InitWeak: {
2142 // If this is storing to the same pointer and has the same size etc.
2143 // replace this load's value with the stored value.
2144 CallInst *Call = cast<CallInst>(Val: Inst);
2145 CallInst *EarlierCall = cast<CallInst>(Val: EarlierInst);
2146 Value *Arg = Call->getArgOperand(i: 0);
2147 Value *EarlierArg = EarlierCall->getArgOperand(i: 0);
2148 switch (PA.getAA()->alias(V1: Arg, V2: EarlierArg)) {
2149 case AliasResult::MustAlias:
2150 Changed = true;
2151 // If the load has a builtin retain, insert a plain retain for it.
2152 if (Class == ARCInstKind::LoadWeakRetained) {
2153 Function *Decl = EP.get(kind: ARCRuntimeEntryPointKind::Retain);
2154 CallInst *CI =
2155 CallInst::Create(Func: Decl, Args: EarlierCall, NameStr: "", InsertBefore: Call->getIterator());
2156 CI->setTailCall();
2157 }
2158 // Zap the fully redundant load.
2159 Call->replaceAllUsesWith(V: EarlierCall->getArgOperand(i: 1));
2160 Call->eraseFromParent();
2161 goto clobbered;
2162 case AliasResult::MayAlias:
2163 case AliasResult::PartialAlias:
2164 goto clobbered;
2165 case AliasResult::NoAlias:
2166 break;
2167 }
2168 break;
2169 }
2170 case ARCInstKind::MoveWeak:
2171 case ARCInstKind::CopyWeak:
2172 // TOOD: Grab the copied value.
2173 goto clobbered;
2174 case ARCInstKind::AutoreleasepoolPush:
2175 case ARCInstKind::None:
2176 case ARCInstKind::IntrinsicUser:
2177 case ARCInstKind::User:
2178 // Weak pointers are only modified through the weak entry points
2179 // (and arbitrary calls, which could call the weak entry points).
2180 break;
2181 default:
2182 // Anything else could modify the weak pointer.
2183 goto clobbered;
2184 }
2185 }
2186 clobbered:;
2187 }
2188
2189 // Then, for each destroyWeak with an alloca operand, check to see if
2190 // the alloca and all its users can be zapped.
2191 for (Instruction &Inst : llvm::make_early_inc_range(Range: instructions(F))) {
2192 ARCInstKind Class = GetBasicARCInstKind(V: &Inst);
2193 if (Class != ARCInstKind::DestroyWeak)
2194 continue;
2195
2196 CallInst *Call = cast<CallInst>(Val: &Inst);
2197 Value *Arg = Call->getArgOperand(i: 0);
2198 if (AllocaInst *Alloca = dyn_cast<AllocaInst>(Val: Arg)) {
2199 for (User *U : Alloca->users()) {
2200 const Instruction *UserInst = cast<Instruction>(Val: U);
2201 switch (GetBasicARCInstKind(V: UserInst)) {
2202 case ARCInstKind::InitWeak:
2203 case ARCInstKind::StoreWeak:
2204 case ARCInstKind::DestroyWeak:
2205 continue;
2206 default:
2207 goto done;
2208 }
2209 }
2210 Changed = true;
2211 for (User *U : llvm::make_early_inc_range(Range: Alloca->users())) {
2212 CallInst *UserInst = cast<CallInst>(Val: U);
2213 switch (GetBasicARCInstKind(V: UserInst)) {
2214 case ARCInstKind::InitWeak:
2215 case ARCInstKind::StoreWeak:
2216 // These functions return their second argument.
2217 UserInst->replaceAllUsesWith(V: UserInst->getArgOperand(i: 1));
2218 break;
2219 case ARCInstKind::DestroyWeak:
2220 // No return value.
2221 break;
2222 default:
2223 llvm_unreachable("alloca really is used!");
2224 }
2225 UserInst->eraseFromParent();
2226 }
2227 Alloca->eraseFromParent();
2228 done:;
2229 }
2230 }
2231}
2232
2233/// Identify program paths which execute sequences of retains and releases which
2234/// can be eliminated.
2235bool ObjCARCOpt::OptimizeSequences(Function &F) {
2236 // Releases, Retains - These are used to store the results of the main flow
2237 // analysis. These use Value* as the key instead of Instruction* so that the
2238 // map stays valid when we get around to rewriting code and calls get
2239 // replaced by arguments.
2240 DenseMap<Value *, RRInfo> Releases;
2241 BlotMapVector<Value *, RRInfo> Retains;
2242
2243 // This is used during the traversal of the function to track the
2244 // states for each identified object at each block.
2245 DenseMap<const BasicBlock *, BBState> BBStates;
2246
2247 // Analyze the CFG of the function, and all instructions.
2248 bool NestingDetected = Visit(F, BBStates, Retains, Releases);
2249
2250 if (DisableRetainReleasePairing)
2251 return false;
2252
2253 // Transform.
2254 bool AnyPairsCompletelyEliminated = PerformCodePlacement(BBStates, Retains,
2255 Releases,
2256 M: F.getParent());
2257
2258 return AnyPairsCompletelyEliminated && NestingDetected;
2259}
2260
2261/// Check if there is a dependent call earlier that does not have anything in
2262/// between the Retain and the call that can affect the reference count of their
2263/// shared pointer argument. Note that Retain need not be in BB.
2264static CallInst *HasSafePathToPredecessorCall(const Value *Arg,
2265 Instruction *Retain,
2266 ProvenanceAnalysis &PA) {
2267 auto *Call = dyn_cast_or_null<CallInst>(Val: findSingleDependency(
2268 Flavor: CanChangeRetainCount, Arg, StartBB: Retain->getParent(), StartInst: Retain, PA));
2269
2270 // Check that the pointer is the return value of the call.
2271 if (!Call || Arg != Call)
2272 return nullptr;
2273
2274 // Check that the call is a regular call.
2275 ARCInstKind Class = GetBasicARCInstKind(V: Call);
2276 return Class == ARCInstKind::CallOrUser || Class == ARCInstKind::Call
2277 ? Call
2278 : nullptr;
2279}
2280
2281/// Find a dependent retain that precedes the given autorelease for which there
2282/// is nothing in between the two instructions that can affect the ref count of
2283/// Arg.
2284static CallInst *
2285FindPredecessorRetainWithSafePath(const Value *Arg, BasicBlock *BB,
2286 Instruction *Autorelease,
2287 ProvenanceAnalysis &PA) {
2288 auto *Retain = dyn_cast_or_null<CallInst>(
2289 Val: findSingleDependency(Flavor: CanChangeRetainCount, Arg, StartBB: BB, StartInst: Autorelease, PA));
2290
2291 // Check that we found a retain with the same argument.
2292 if (!Retain || !IsRetain(Class: GetBasicARCInstKind(V: Retain)) ||
2293 GetArgRCIdentityRoot(Inst: Retain) != Arg) {
2294 return nullptr;
2295 }
2296
2297 return Retain;
2298}
2299
2300/// Look for an ``autorelease'' instruction dependent on Arg such that there are
2301/// no instructions dependent on Arg that need a positive ref count in between
2302/// the autorelease and the ret.
2303static CallInst *FindPredecessorAutoreleaseWithSafePath(
2304 const Value *Arg, BasicBlock *BB, ReturnInst *Ret, ProvenanceAnalysis &PA) {
2305 auto *Autorelease = dyn_cast_or_null<CallInst>(
2306 Val: findSingleDependency(Flavor: NeedsPositiveRetainCount, Arg, StartBB: BB, StartInst: Ret, PA));
2307
2308 if (!Autorelease)
2309 return nullptr;
2310 ARCInstKind AutoreleaseClass = GetBasicARCInstKind(V: Autorelease);
2311 if (!IsAutorelease(Class: AutoreleaseClass))
2312 return nullptr;
2313 if (GetArgRCIdentityRoot(Inst: Autorelease) != Arg)
2314 return nullptr;
2315
2316 return Autorelease;
2317}
2318
2319/// Look for this pattern:
2320/// \code
2321/// %call = call i8* @something(...)
2322/// %2 = call i8* @objc_retain(i8* %call)
2323/// %3 = call i8* @objc_autorelease(i8* %2)
2324/// ret i8* %3
2325/// \endcode
2326/// And delete the retain and autorelease.
2327void ObjCARCOpt::OptimizeReturns(Function &F) {
2328 if (!F.getReturnType()->isPointerTy())
2329 return;
2330
2331 LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeReturns ==\n");
2332
2333 for (BasicBlock &BB: F) {
2334 ReturnInst *Ret = dyn_cast<ReturnInst>(Val: &BB.back());
2335 if (!Ret)
2336 continue;
2337
2338 LLVM_DEBUG(dbgs() << "Visiting: " << *Ret << "\n");
2339
2340 const Value *Arg = GetRCIdentityRoot(V: Ret->getOperand(i_nocapture: 0));
2341
2342 // Look for an ``autorelease'' instruction that is a predecessor of Ret and
2343 // dependent on Arg such that there are no instructions dependent on Arg
2344 // that need a positive ref count in between the autorelease and Ret.
2345 CallInst *Autorelease =
2346 FindPredecessorAutoreleaseWithSafePath(Arg, BB: &BB, Ret, PA);
2347
2348 if (!Autorelease)
2349 continue;
2350
2351 CallInst *Retain = FindPredecessorRetainWithSafePath(
2352 Arg, BB: Autorelease->getParent(), Autorelease, PA);
2353
2354 if (!Retain)
2355 continue;
2356
2357 // Check that there is nothing that can affect the reference count
2358 // between the retain and the call. Note that Retain need not be in BB.
2359 CallInst *Call = HasSafePathToPredecessorCall(Arg, Retain, PA);
2360
2361 // Don't remove retainRV/autoreleaseRV pairs if the call isn't a tail call.
2362 if (!Call ||
2363 (!Call->isTailCall() &&
2364 GetBasicARCInstKind(V: Retain) == ARCInstKind::RetainRV &&
2365 GetBasicARCInstKind(V: Autorelease) == ARCInstKind::AutoreleaseRV))
2366 continue;
2367
2368 // If so, we can zap the retain and autorelease.
2369 Changed = true;
2370 ++NumRets;
2371 LLVM_DEBUG(dbgs() << "Erasing: " << *Retain << "\nErasing: " << *Autorelease
2372 << "\n");
2373 BundledInsts->eraseInst(CI: Retain);
2374 EraseInstruction(CI: Autorelease);
2375 }
2376}
2377
2378#ifndef NDEBUG
2379void
2380ObjCARCOpt::GatherStatistics(Function &F, bool AfterOptimization) {
2381 Statistic &NumRetains =
2382 AfterOptimization ? NumRetainsAfterOpt : NumRetainsBeforeOpt;
2383 Statistic &NumReleases =
2384 AfterOptimization ? NumReleasesAfterOpt : NumReleasesBeforeOpt;
2385
2386 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
2387 Instruction *Inst = &*I++;
2388 switch (GetBasicARCInstKind(Inst)) {
2389 default:
2390 break;
2391 case ARCInstKind::Retain:
2392 ++NumRetains;
2393 break;
2394 case ARCInstKind::Release:
2395 ++NumReleases;
2396 break;
2397 }
2398 }
2399}
2400#endif
2401
2402void ObjCARCOpt::init(Function &F) {
2403 if (!EnableARCOpts)
2404 return;
2405
2406 // Intuitively, objc_retain and others are nocapture, however in practice
2407 // they are not, because they return their argument value. And objc_release
2408 // calls finalizers which can have arbitrary side effects.
2409 MDKindCache.init(Mod: F.getParent());
2410
2411 // Initialize our runtime entry point cache.
2412 EP.init(M: F.getParent());
2413
2414 // Compute which blocks are in which funclet.
2415 if (F.hasPersonalityFn() &&
2416 isScopedEHPersonality(Pers: classifyEHPersonality(Pers: F.getPersonalityFn())))
2417 BlockEHColors = colorEHFunclets(F);
2418}
2419
2420bool ObjCARCOpt::run(Function &F, AAResults &AA) {
2421 if (!EnableARCOpts)
2422 return false;
2423
2424 Changed = CFGChanged = false;
2425 BundledRetainClaimRVs BRV(EP, /*ContractPass=*/false, /*UseClaimRV=*/false);
2426 BundledInsts = &BRV;
2427
2428 LLVM_DEBUG(dbgs() << "<<< ObjCARCOpt: Visiting Function: " << F.getName()
2429 << " >>>"
2430 "\n");
2431
2432 std::pair<bool, bool> R = BundledInsts->insertAfterInvokes(F, DT: nullptr);
2433 Changed |= R.first;
2434 CFGChanged |= R.second;
2435
2436 PA.setAA(&AA);
2437
2438#ifndef NDEBUG
2439 if (AreStatisticsEnabled()) {
2440 GatherStatistics(F, false);
2441 }
2442#endif
2443
2444 // This pass performs several distinct transformations. As a compile-time aid
2445 // when compiling code that isn't ObjC, skip these if the relevant ObjC
2446 // library functions aren't declared.
2447
2448 // Preliminary optimizations. This also computes UsedInThisFunction.
2449 OptimizeIndividualCalls(F);
2450
2451 // Optimizations for weak pointers.
2452 if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::LoadWeak)) |
2453 (1 << unsigned(ARCInstKind::LoadWeakRetained)) |
2454 (1 << unsigned(ARCInstKind::StoreWeak)) |
2455 (1 << unsigned(ARCInstKind::InitWeak)) |
2456 (1 << unsigned(ARCInstKind::CopyWeak)) |
2457 (1 << unsigned(ARCInstKind::MoveWeak)) |
2458 (1 << unsigned(ARCInstKind::DestroyWeak))))
2459 OptimizeWeakCalls(F);
2460
2461 // Optimizations for retain+release pairs.
2462 if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::Retain)) |
2463 (1 << unsigned(ARCInstKind::RetainRV)) |
2464 (1 << unsigned(ARCInstKind::RetainBlock))))
2465 if (UsedInThisFunction & (1 << unsigned(ARCInstKind::Release)))
2466 // Run OptimizeSequences until it either stops making changes or
2467 // no retain+release pair nesting is detected.
2468 while (OptimizeSequences(F)) {}
2469
2470 // Optimizations if objc_autorelease is used.
2471 if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::Autorelease)) |
2472 (1 << unsigned(ARCInstKind::AutoreleaseRV))))
2473 OptimizeReturns(F);
2474
2475 // Optimizations for autorelease pools.
2476 if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::AutoreleasepoolPush)) |
2477 (1 << unsigned(ARCInstKind::AutoreleasepoolPop))))
2478 OptimizeAutoreleasePools(F);
2479
2480 // Gather statistics after optimization.
2481#ifndef NDEBUG
2482 if (AreStatisticsEnabled()) {
2483 GatherStatistics(F, true);
2484 }
2485#endif
2486
2487 LLVM_DEBUG(dbgs() << "\n");
2488
2489 return Changed;
2490}
2491
2492/// Interprocedurally determine if calls made by the given call site can
2493/// possibly produce autoreleases.
2494bool MayAutorelease(const CallBase &CB, unsigned Depth = 0) {
2495 if (CB.onlyReadsMemory())
2496 return false;
2497
2498 // This recursion depth limit is arbitrary. It's just great
2499 // enough to cover known interesting testcases.
2500 if (Depth > 5)
2501 return true;
2502
2503 if (const Function *Callee = CB.getCalledFunction()) {
2504 if (!Callee->hasExactDefinition())
2505 return true;
2506 for (const BasicBlock &BB : *Callee) {
2507 for (const Instruction &I : BB) {
2508 // TODO: Ignore all instructions between autorelease pools
2509 ARCInstKind InstKind = GetBasicARCInstKind(V: &I);
2510 switch (InstKind) {
2511 case ARCInstKind::Autorelease:
2512 case ARCInstKind::AutoreleaseRV:
2513 case ARCInstKind::FusedRetainAutorelease:
2514 case ARCInstKind::FusedRetainAutoreleaseRV:
2515 case ARCInstKind::LoadWeak:
2516 // These may produce autoreleases
2517 return true;
2518
2519 case ARCInstKind::Retain:
2520 case ARCInstKind::RetainRV:
2521 case ARCInstKind::UnsafeClaimRV:
2522 case ARCInstKind::RetainBlock:
2523 case ARCInstKind::Release:
2524 case ARCInstKind::NoopCast:
2525 case ARCInstKind::LoadWeakRetained:
2526 case ARCInstKind::StoreWeak:
2527 case ARCInstKind::InitWeak:
2528 case ARCInstKind::MoveWeak:
2529 case ARCInstKind::CopyWeak:
2530 case ARCInstKind::DestroyWeak:
2531 case ARCInstKind::StoreStrong:
2532 case ARCInstKind::AutoreleasepoolPush:
2533 case ARCInstKind::AutoreleasepoolPop:
2534 // These ObjC runtime functions don't produce autoreleases
2535 break;
2536
2537 case ARCInstKind::CallOrUser:
2538 case ARCInstKind::Call:
2539 // For non-ObjC function calls, recursively analyze
2540 if (MayAutorelease(CB: cast<CallBase>(Val: I), Depth: Depth + 1))
2541 return true;
2542 break;
2543
2544 case ARCInstKind::IntrinsicUser:
2545 case ARCInstKind::User:
2546 case ARCInstKind::None:
2547 // These are not relevant for autorelease analysis
2548 break;
2549 }
2550 }
2551 }
2552 return false;
2553 }
2554
2555 return true;
2556}
2557
2558/// Optimize autorelease pools by eliminating empty push/pop pairs.
2559void ObjCARCOpt::OptimizeAutoreleasePools(Function &F) {
2560 LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeAutoreleasePools ==\n");
2561
2562 OptimizationRemarkEmitter ORE(&F);
2563
2564 // Process each basic block independently.
2565 // TODO: Can we optimize inter-block autorelease pool pairs?
2566 // This would involve tracking autorelease pool state across blocks.
2567 for (BasicBlock &BB : F) {
2568 // Use a stack to track nested autorelease pools
2569 SmallVector<std::pair<CallInst *, bool>, 4>
2570 PoolStack; // {push_inst, has_autorelease_in_scope}
2571
2572 for (Instruction &Inst : llvm::make_early_inc_range(Range&: BB)) {
2573 ARCInstKind Class = GetBasicARCInstKind(V: &Inst);
2574
2575 switch (Class) {
2576 case ARCInstKind::AutoreleasepoolPush: {
2577 // Start tracking a new autorelease pool scope
2578 auto *Push = cast<CallInst>(Val: &Inst);
2579 PoolStack.push_back(
2580 Elt: {Push, false}); // {push_inst, has_autorelease_in_scope}
2581 LLVM_DEBUG(dbgs() << "Found autorelease pool push: " << *Push << "\n");
2582 break;
2583 }
2584
2585 case ARCInstKind::AutoreleasepoolPop: {
2586 auto *Pop = cast<CallInst>(Val: &Inst);
2587
2588 if (PoolStack.empty())
2589 break;
2590
2591 auto &TopPool = PoolStack.back();
2592 CallInst *PendingPush = TopPool.first;
2593 bool HasAutoreleaseInScope = TopPool.second;
2594
2595 // Pop the stack - remove this pool scope
2596 PoolStack.pop_back();
2597
2598 // Bail if this pop doesn't match the pending push
2599 if (Pop->getArgOperand(i: 0)->stripPointerCasts() != PendingPush)
2600 break;
2601
2602 // Bail if there were autoreleases in this scope
2603 if (HasAutoreleaseInScope)
2604 break;
2605
2606 // Optimize: eliminate this empty autorelease pool pair
2607 ORE.emit(RemarkBuilder: [&]() {
2608 return OptimizationRemark(DEBUG_TYPE, "AutoreleasePoolElimination",
2609 PendingPush)
2610 << "eliminated empty autorelease pool pair";
2611 });
2612
2613 // Replace all uses of push with poison before deletion
2614 PendingPush->replaceAllUsesWith(
2615 V: PoisonValue::get(T: PendingPush->getType()));
2616
2617 Pop->eraseFromParent();
2618 PendingPush->eraseFromParent();
2619
2620 Changed = true;
2621 ++NumNoops;
2622 break;
2623 }
2624 case ARCInstKind::CallOrUser:
2625 case ARCInstKind::Call:
2626 if (!MayAutorelease(CB: cast<CallBase>(Val&: Inst)))
2627 break;
2628 [[fallthrough]];
2629 case ARCInstKind::Autorelease:
2630 case ARCInstKind::AutoreleaseRV:
2631 case ARCInstKind::FusedRetainAutorelease:
2632 case ARCInstKind::FusedRetainAutoreleaseRV:
2633 case ARCInstKind::LoadWeak: {
2634 // Track that we have autorelease calls in the current pool scope
2635 if (!PoolStack.empty()) {
2636 PoolStack.back().second = true; // Set has_autorelease_in_scope = true
2637 LLVM_DEBUG(
2638 dbgs()
2639 << "Found autorelease or potential autorelease in pool scope: "
2640 << Inst << "\n");
2641 }
2642 break;
2643 }
2644
2645 // Enumerate all remaining ARCInstKind cases explicitly
2646 case ARCInstKind::Retain:
2647 case ARCInstKind::RetainRV:
2648 case ARCInstKind::UnsafeClaimRV:
2649 case ARCInstKind::RetainBlock:
2650 case ARCInstKind::Release:
2651 case ARCInstKind::NoopCast:
2652 case ARCInstKind::LoadWeakRetained:
2653 case ARCInstKind::StoreWeak:
2654 case ARCInstKind::InitWeak:
2655 case ARCInstKind::MoveWeak:
2656 case ARCInstKind::CopyWeak:
2657 case ARCInstKind::DestroyWeak:
2658 case ARCInstKind::StoreStrong:
2659 case ARCInstKind::IntrinsicUser:
2660 case ARCInstKind::User:
2661 case ARCInstKind::None:
2662 // These instruction kinds don't affect autorelease pool optimization
2663 break;
2664 }
2665 }
2666 }
2667}
2668
2669/// @}
2670///
2671
2672PreservedAnalyses ObjCARCOptPass::run(Function &F,
2673 FunctionAnalysisManager &AM) {
2674 ObjCARCOpt OCAO;
2675 OCAO.init(F);
2676
2677 bool Changed = OCAO.run(F, AA&: AM.getResult<AAManager>(IR&: F));
2678 bool CFGChanged = OCAO.hasCFGChanged();
2679 if (Changed) {
2680 PreservedAnalyses PA;
2681 if (!CFGChanged)
2682 PA.preserveSet<CFGAnalyses>();
2683 return PA;
2684 }
2685 return PreservedAnalyses::all();
2686}
2687