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 auto BBI = BBStates.find(Val: Succ);
1266 assert(BBI != BBStates.end());
1267 const BottomUpPtrState &SuccS = BBI->second.getPtrBottomUpState(Arg);
1268 const Sequence SuccSSeq = SuccS.GetSeq();
1269
1270 // If bottom up, the pointer is in an S_None state, clear the sequence
1271 // progress since the sequence in the bottom up state finished
1272 // suggesting a mismatch in between retains/releases. This is true for
1273 // all three cases that we are handling here: S_Retain, S_Use, and
1274 // S_CanRelease.
1275 if (SuccSSeq == S_None) {
1276 S.ClearSequenceProgress();
1277 continue;
1278 }
1279
1280 // If we have S_Use or S_CanRelease, perform our check for cfg hazard
1281 // checks.
1282 const bool SuccSRRIKnownSafe = SuccS.IsKnownSafe();
1283
1284 // *NOTE* We do not use Seq from above here since we are allowing for
1285 // S.GetSeq() to change while we are visiting basic blocks.
1286 switch(S.GetSeq()) {
1287 case S_Use: {
1288 bool ShouldContinue = false;
1289 CheckForUseCFGHazard(SuccSSeq, SuccSRRIKnownSafe, S, SomeSuccHasSame,
1290 AllSuccsHaveSame, NotAllSeqEqualButKnownSafe,
1291 ShouldContinue);
1292 if (ShouldContinue)
1293 continue;
1294 break;
1295 }
1296 case S_CanRelease:
1297 CheckForCanReleaseCFGHazard(SuccSSeq, SuccSRRIKnownSafe, S,
1298 SomeSuccHasSame, AllSuccsHaveSame,
1299 NotAllSeqEqualButKnownSafe);
1300 break;
1301 case S_Retain:
1302 case S_None:
1303 case S_Stop:
1304 case S_MovableRelease:
1305 break;
1306 }
1307 }
1308
1309 // If the state at the other end of any of the successor edges
1310 // matches the current state, require all edges to match. This
1311 // guards against loops in the middle of a sequence.
1312 if (SomeSuccHasSame && !AllSuccsHaveSame) {
1313 S.ClearSequenceProgress();
1314 } else if (NotAllSeqEqualButKnownSafe) {
1315 // If we would have cleared the state foregoing the fact that we are known
1316 // safe, stop code motion. This is because whether or not it is safe to
1317 // remove RR pairs via KnownSafe is an orthogonal concept to whether we
1318 // are allowed to perform code motion.
1319 S.SetCFGHazardAfflicted(true);
1320 }
1321 }
1322}
1323
1324bool ObjCARCOpt::VisitInstructionBottomUp(
1325 Instruction *Inst, BasicBlock *BB, BlotMapVector<Value *, RRInfo> &Retains,
1326 BBState &MyStates) {
1327 bool NestingDetected = false;
1328 ARCInstKind Class = GetARCInstKind(V: Inst);
1329 const Value *Arg = nullptr;
1330
1331 LLVM_DEBUG(dbgs() << " Class: " << Class << "\n");
1332
1333 switch (Class) {
1334 case ARCInstKind::Release: {
1335 Arg = GetArgRCIdentityRoot(Inst);
1336
1337 BottomUpPtrState &S = MyStates.getPtrBottomUpState(Arg);
1338 NestingDetected |= S.InitBottomUp(Cache&: MDKindCache, I: Inst);
1339 break;
1340 }
1341 case ARCInstKind::RetainBlock:
1342 // In OptimizeIndividualCalls, we have strength reduced all optimizable
1343 // objc_retainBlocks to objc_retains. Thus at this point any
1344 // objc_retainBlocks that we see are not optimizable.
1345 break;
1346 case ARCInstKind::Retain:
1347 case ARCInstKind::RetainRV: {
1348 Arg = GetArgRCIdentityRoot(Inst);
1349 BottomUpPtrState &S = MyStates.getPtrBottomUpState(Arg);
1350 if (S.MatchWithRetain()) {
1351 // Don't do retain+release tracking for ARCInstKind::RetainRV, because
1352 // it's better to let it remain as the first instruction after a call.
1353 if (Class != ARCInstKind::RetainRV) {
1354 LLVM_DEBUG(dbgs() << " Matching with: " << *Inst << "\n");
1355 Retains[Inst] = S.GetRRInfo();
1356 }
1357 S.ClearSequenceProgress();
1358 }
1359 // A retain moving bottom up can be a use.
1360 break;
1361 }
1362 case ARCInstKind::AutoreleasepoolPop:
1363 // Conservatively, clear MyStates for all known pointers.
1364 MyStates.clearBottomUpPointers();
1365 return NestingDetected;
1366 case ARCInstKind::AutoreleasepoolPush:
1367 case ARCInstKind::None:
1368 // These are irrelevant.
1369 return NestingDetected;
1370 default:
1371 break;
1372 }
1373
1374 // Consider any other possible effects of this instruction on each
1375 // pointer being tracked.
1376 for (auto MI = MyStates.bottom_up_ptr_begin(),
1377 ME = MyStates.bottom_up_ptr_end();
1378 MI != ME; ++MI) {
1379 const Value *Ptr = MI->first;
1380 if (Ptr == Arg)
1381 continue; // Handled above.
1382 BottomUpPtrState &S = MI->second;
1383
1384 if (S.HandlePotentialAlterRefCount(Inst, Ptr, PA, Class))
1385 continue;
1386
1387 S.HandlePotentialUse(BB, Inst, Ptr, PA, Class);
1388 }
1389
1390 return NestingDetected;
1391}
1392
1393bool ObjCARCOpt::VisitBottomUp(BasicBlock *BB,
1394 DenseMap<const BasicBlock *, BBState> &BBStates,
1395 BlotMapVector<Value *, RRInfo> &Retains) {
1396 LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::VisitBottomUp ==\n");
1397
1398 bool NestingDetected = false;
1399 BBState &MyStates = BBStates[BB];
1400
1401 // Merge the states from each successor to compute the initial state
1402 // for the current block.
1403 BBState::edge_iterator SI(MyStates.succ_begin()),
1404 SE(MyStates.succ_end());
1405 if (SI != SE) {
1406 const BasicBlock *Succ = *SI;
1407 auto I = BBStates.find(Val: Succ);
1408 assert(I != BBStates.end());
1409 MyStates.InitFromSucc(Other: I->second);
1410 ++SI;
1411 for (; SI != SE; ++SI) {
1412 Succ = *SI;
1413 I = BBStates.find(Val: Succ);
1414 assert(I != BBStates.end());
1415 MyStates.MergeSucc(Other: I->second);
1416 }
1417 }
1418
1419 LLVM_DEBUG(dbgs() << "Before:\n"
1420 << BBStates[BB] << "\n"
1421 << "Performing Dataflow:\n");
1422
1423 // Visit all the instructions, bottom-up.
1424 for (BasicBlock::iterator I = BB->end(), E = BB->begin(); I != E; --I) {
1425 Instruction *Inst = &*std::prev(x: I);
1426
1427 // Invoke instructions are visited as part of their successors (below).
1428 if (isa<InvokeInst>(Val: Inst))
1429 continue;
1430
1431 LLVM_DEBUG(dbgs() << " Visiting " << *Inst << "\n");
1432
1433 NestingDetected |= VisitInstructionBottomUp(Inst, BB, Retains, MyStates);
1434
1435 // Bail out if the number of pointers being tracked becomes too large so
1436 // that this pass can complete in a reasonable amount of time.
1437 if (MyStates.bottom_up_ptr_list_size() > MaxPtrStates) {
1438 DisableRetainReleasePairing = true;
1439 return false;
1440 }
1441 }
1442
1443 // If there's a predecessor with an invoke, visit the invoke as if it were
1444 // part of this block, since we can't insert code after an invoke in its own
1445 // block, and we don't want to split critical edges.
1446 for (BBState::edge_iterator PI(MyStates.pred_begin()),
1447 PE(MyStates.pred_end()); PI != PE; ++PI) {
1448 BasicBlock *Pred = *PI;
1449 if (InvokeInst *II = dyn_cast<InvokeInst>(Val: &Pred->back()))
1450 NestingDetected |= VisitInstructionBottomUp(Inst: II, BB, Retains, MyStates);
1451 }
1452
1453 LLVM_DEBUG(dbgs() << "\nFinal State:\n" << BBStates[BB] << "\n");
1454
1455 return NestingDetected;
1456}
1457
1458// Fill ReleaseInsertPtToRCIdentityRoots, which is a map from insertion points
1459// to the set of RC identity roots that would be released by the release calls
1460// moved to the insertion points.
1461static void collectReleaseInsertPts(
1462 const BlotMapVector<Value *, RRInfo> &Retains,
1463 DenseMap<const Instruction *, SmallPtrSet<const Value *, 2>>
1464 &ReleaseInsertPtToRCIdentityRoots) {
1465 for (const auto &P : Retains) {
1466 // Retains is a map from an objc_retain call to a RRInfo of the RC identity
1467 // root of the call. Get the RC identity root of the objc_retain call.
1468 Instruction *Retain = cast<Instruction>(Val: P.first);
1469 Value *Root = GetRCIdentityRoot(V: Retain->getOperand(i: 0));
1470 // Collect all the insertion points of the objc_release calls that release
1471 // the RC identity root of the objc_retain call.
1472 for (const Instruction *InsertPt : P.second.ReverseInsertPts)
1473 ReleaseInsertPtToRCIdentityRoots[InsertPt].insert(Ptr: Root);
1474 }
1475}
1476
1477// Get the RC identity roots from an insertion point of an objc_release call.
1478// Return nullptr if the passed instruction isn't an insertion point.
1479static const SmallPtrSet<const Value *, 2> *
1480getRCIdentityRootsFromReleaseInsertPt(
1481 const Instruction *InsertPt,
1482 const DenseMap<const Instruction *, SmallPtrSet<const Value *, 2>>
1483 &ReleaseInsertPtToRCIdentityRoots) {
1484 auto I = ReleaseInsertPtToRCIdentityRoots.find(Val: InsertPt);
1485 if (I == ReleaseInsertPtToRCIdentityRoots.end())
1486 return nullptr;
1487 return &I->second;
1488}
1489
1490bool ObjCARCOpt::VisitInstructionTopDown(
1491 Instruction *Inst, DenseMap<Value *, RRInfo> &Releases, BBState &MyStates,
1492 const DenseMap<const Instruction *, SmallPtrSet<const Value *, 2>>
1493 &ReleaseInsertPtToRCIdentityRoots) {
1494 bool NestingDetected = false;
1495 ARCInstKind Class = GetARCInstKind(V: Inst);
1496 const Value *Arg = nullptr;
1497
1498 // Make sure a call to objc_retain isn't moved past insertion points of calls
1499 // to objc_release.
1500 if (const SmallPtrSet<const Value *, 2> *Roots =
1501 getRCIdentityRootsFromReleaseInsertPt(
1502 InsertPt: Inst, ReleaseInsertPtToRCIdentityRoots))
1503 for (const auto *Root : *Roots) {
1504 TopDownPtrState &S = MyStates.getPtrTopDownState(Arg: Root);
1505 // Disable code motion if the current position is S_Retain to prevent
1506 // moving the objc_retain call past objc_release calls. If it's
1507 // S_CanRelease or larger, it's not necessary to disable code motion as
1508 // the insertion points that prevent the objc_retain call from moving down
1509 // should have been set already.
1510 if (S.GetSeq() == S_Retain)
1511 S.SetCFGHazardAfflicted(true);
1512 }
1513
1514 LLVM_DEBUG(dbgs() << " Class: " << Class << "\n");
1515
1516 switch (Class) {
1517 case ARCInstKind::RetainBlock:
1518 // In OptimizeIndividualCalls, we have strength reduced all optimizable
1519 // objc_retainBlocks to objc_retains. Thus at this point any
1520 // objc_retainBlocks that we see are not optimizable. We need to break since
1521 // a retain can be a potential use.
1522 break;
1523 case ARCInstKind::Retain:
1524 case ARCInstKind::RetainRV: {
1525 Arg = GetArgRCIdentityRoot(Inst);
1526 TopDownPtrState &S = MyStates.getPtrTopDownState(Arg);
1527 NestingDetected |= S.InitTopDown(Kind: Class, I: Inst);
1528 // A retain can be a potential use; proceed to the generic checking
1529 // code below.
1530 break;
1531 }
1532 case ARCInstKind::Release: {
1533 Arg = GetArgRCIdentityRoot(Inst);
1534 TopDownPtrState &S = MyStates.getPtrTopDownState(Arg);
1535 // Try to form a tentative pair in between this release instruction and the
1536 // top down pointers that we are tracking.
1537 if (S.MatchWithRelease(Cache&: MDKindCache, Release: Inst)) {
1538 // If we succeed, copy S's RRInfo into the Release -> {Retain Set
1539 // Map}. Then we clear S.
1540 LLVM_DEBUG(dbgs() << " Matching with: " << *Inst << "\n");
1541 Releases[Inst] = S.GetRRInfo();
1542 S.ClearSequenceProgress();
1543 }
1544 break;
1545 }
1546 case ARCInstKind::AutoreleasepoolPop:
1547 // Conservatively, clear MyStates for all known pointers.
1548 MyStates.clearTopDownPointers();
1549 return false;
1550 case ARCInstKind::AutoreleasepoolPush:
1551 case ARCInstKind::None:
1552 // These can not be uses of
1553 return false;
1554 default:
1555 break;
1556 }
1557
1558 // Consider any other possible effects of this instruction on each
1559 // pointer being tracked.
1560 for (auto MI = MyStates.top_down_ptr_begin(),
1561 ME = MyStates.top_down_ptr_end();
1562 MI != ME; ++MI) {
1563 const Value *Ptr = MI->first;
1564 if (Ptr == Arg)
1565 continue; // Handled above.
1566 TopDownPtrState &S = MI->second;
1567 if (S.HandlePotentialAlterRefCount(Inst, Ptr, PA, Class, BundledRVs: *BundledInsts))
1568 continue;
1569
1570 S.HandlePotentialUse(Inst, Ptr, PA, Class);
1571 }
1572
1573 return NestingDetected;
1574}
1575
1576bool ObjCARCOpt::VisitTopDown(
1577 BasicBlock *BB, DenseMap<const BasicBlock *, BBState> &BBStates,
1578 DenseMap<Value *, RRInfo> &Releases,
1579 const DenseMap<const Instruction *, SmallPtrSet<const Value *, 2>>
1580 &ReleaseInsertPtToRCIdentityRoots) {
1581 LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::VisitTopDown ==\n");
1582 bool NestingDetected = false;
1583 BBState &MyStates = BBStates[BB];
1584
1585 // Merge the states from each predecessor to compute the initial state
1586 // for the current block.
1587 BBState::edge_iterator PI(MyStates.pred_begin()),
1588 PE(MyStates.pred_end());
1589 if (PI != PE) {
1590 const BasicBlock *Pred = *PI;
1591 auto I = BBStates.find(Val: Pred);
1592 assert(I != BBStates.end());
1593 MyStates.InitFromPred(Other: I->second);
1594 ++PI;
1595 for (; PI != PE; ++PI) {
1596 Pred = *PI;
1597 I = BBStates.find(Val: Pred);
1598 assert(I != BBStates.end());
1599 MyStates.MergePred(Other: I->second);
1600 }
1601 }
1602
1603 // Check that BB and MyStates have the same number of predecessors. This
1604 // prevents retain calls that live outside a loop from being moved into the
1605 // loop.
1606 if (!BB->hasNPredecessors(N: MyStates.pred_end() - MyStates.pred_begin()))
1607 for (auto I = MyStates.top_down_ptr_begin(),
1608 E = MyStates.top_down_ptr_end();
1609 I != E; ++I)
1610 I->second.SetCFGHazardAfflicted(true);
1611
1612 LLVM_DEBUG(dbgs() << "Before:\n"
1613 << BBStates[BB] << "\n"
1614 << "Performing Dataflow:\n");
1615
1616 // Visit all the instructions, top-down.
1617 for (Instruction &Inst : *BB) {
1618 LLVM_DEBUG(dbgs() << " Visiting " << Inst << "\n");
1619
1620 NestingDetected |= VisitInstructionTopDown(
1621 Inst: &Inst, Releases, MyStates, ReleaseInsertPtToRCIdentityRoots);
1622
1623 // Bail out if the number of pointers being tracked becomes too large so
1624 // that this pass can complete in a reasonable amount of time.
1625 if (MyStates.top_down_ptr_list_size() > MaxPtrStates) {
1626 DisableRetainReleasePairing = true;
1627 return false;
1628 }
1629 }
1630
1631 LLVM_DEBUG(dbgs() << "\nState Before Checking for CFG Hazards:\n"
1632 << BBStates[BB] << "\n\n");
1633 CheckForCFGHazards(BB, BBStates, MyStates);
1634 LLVM_DEBUG(dbgs() << "Final State:\n" << BBStates[BB] << "\n");
1635 return NestingDetected;
1636}
1637
1638static void
1639ComputePostOrders(Function &F,
1640 SmallVectorImpl<BasicBlock *> &PostOrder,
1641 SmallVectorImpl<BasicBlock *> &ReverseCFGPostOrder,
1642 unsigned NoObjCARCExceptionsMDKind,
1643 DenseMap<const BasicBlock *, BBState> &BBStates) {
1644 /// The visited set, for doing DFS walks.
1645 SmallPtrSet<BasicBlock *, 16> Visited;
1646
1647 // Do DFS, computing the PostOrder.
1648 SmallPtrSet<BasicBlock *, 16> OnStack;
1649 SmallVector<std::pair<BasicBlock *, succ_iterator>, 16> SuccStack;
1650
1651 // Functions always have exactly one entry block, and we don't have
1652 // any other block that we treat like an entry block.
1653 BasicBlock *EntryBB = &F.getEntryBlock();
1654 BBState &MyStates = BBStates[EntryBB];
1655 MyStates.SetAsEntry();
1656 SuccStack.push_back(Elt: std::make_pair(x&: EntryBB, y: succ_begin(BB: EntryBB)));
1657 Visited.insert(Ptr: EntryBB);
1658 OnStack.insert(Ptr: EntryBB);
1659 do {
1660 dfs_next_succ:
1661 BasicBlock *CurrBB = SuccStack.back().first;
1662 succ_iterator SE = succ_end(I: CurrBB->getTerminator());
1663
1664 while (SuccStack.back().second != SE) {
1665 BasicBlock *SuccBB = *SuccStack.back().second++;
1666 if (Visited.insert(Ptr: SuccBB).second) {
1667 SuccStack.push_back(Elt: std::make_pair(x&: SuccBB, y: succ_begin(BB: SuccBB)));
1668 BBStates[CurrBB].addSucc(Succ: SuccBB);
1669 BBState &SuccStates = BBStates[SuccBB];
1670 SuccStates.addPred(Pred: CurrBB);
1671 OnStack.insert(Ptr: SuccBB);
1672 goto dfs_next_succ;
1673 }
1674
1675 if (!OnStack.count(Ptr: SuccBB)) {
1676 BBStates[CurrBB].addSucc(Succ: SuccBB);
1677 BBStates[SuccBB].addPred(Pred: CurrBB);
1678 }
1679 }
1680 OnStack.erase(Ptr: CurrBB);
1681 PostOrder.push_back(Elt: CurrBB);
1682 SuccStack.pop_back();
1683 } while (!SuccStack.empty());
1684
1685 Visited.clear();
1686
1687 // Do reverse-CFG DFS, computing the reverse-CFG PostOrder.
1688 // Functions may have many exits, and there also blocks which we treat
1689 // as exits due to ignored edges.
1690 SmallVector<std::pair<BasicBlock *, BBState::edge_iterator>, 16> PredStack;
1691 for (BasicBlock &ExitBB : F) {
1692 BBState &MyStates = BBStates[&ExitBB];
1693 if (!MyStates.isExit())
1694 continue;
1695
1696 MyStates.SetAsExit();
1697
1698 PredStack.push_back(Elt: std::make_pair(x: &ExitBB, y: MyStates.pred_begin()));
1699 Visited.insert(Ptr: &ExitBB);
1700 while (!PredStack.empty()) {
1701 reverse_dfs_next_succ:
1702 BBState::edge_iterator PE = BBStates[PredStack.back().first].pred_end();
1703 while (PredStack.back().second != PE) {
1704 BasicBlock *BB = *PredStack.back().second++;
1705 if (Visited.insert(Ptr: BB).second) {
1706 PredStack.push_back(Elt: std::make_pair(x&: BB, y: BBStates[BB].pred_begin()));
1707 goto reverse_dfs_next_succ;
1708 }
1709 }
1710 ReverseCFGPostOrder.push_back(Elt: PredStack.pop_back_val().first);
1711 }
1712 }
1713}
1714
1715// Visit the function both top-down and bottom-up.
1716bool ObjCARCOpt::Visit(Function &F,
1717 DenseMap<const BasicBlock *, BBState> &BBStates,
1718 BlotMapVector<Value *, RRInfo> &Retains,
1719 DenseMap<Value *, RRInfo> &Releases) {
1720 // Use reverse-postorder traversals, because we magically know that loops
1721 // will be well behaved, i.e. they won't repeatedly call retain on a single
1722 // pointer without doing a release. We can't use the ReversePostOrderTraversal
1723 // class here because we want the reverse-CFG postorder to consider each
1724 // function exit point, and we want to ignore selected cycle edges.
1725 SmallVector<BasicBlock *, 16> PostOrder;
1726 SmallVector<BasicBlock *, 16> ReverseCFGPostOrder;
1727 ComputePostOrders(F, PostOrder, ReverseCFGPostOrder,
1728 NoObjCARCExceptionsMDKind: MDKindCache.get(ID: ARCMDKindID::NoObjCARCExceptions),
1729 BBStates);
1730
1731 // Use reverse-postorder on the reverse CFG for bottom-up.
1732 bool BottomUpNestingDetected = false;
1733 for (BasicBlock *BB : llvm::reverse(C&: ReverseCFGPostOrder)) {
1734 BottomUpNestingDetected |= VisitBottomUp(BB, BBStates, Retains);
1735 if (DisableRetainReleasePairing)
1736 return false;
1737 }
1738
1739 DenseMap<const Instruction *, SmallPtrSet<const Value *, 2>>
1740 ReleaseInsertPtToRCIdentityRoots;
1741 collectReleaseInsertPts(Retains, ReleaseInsertPtToRCIdentityRoots);
1742
1743 // Use reverse-postorder for top-down.
1744 bool TopDownNestingDetected = false;
1745 for (BasicBlock *BB : llvm::reverse(C&: PostOrder)) {
1746 TopDownNestingDetected |=
1747 VisitTopDown(BB, BBStates, Releases, ReleaseInsertPtToRCIdentityRoots);
1748 if (DisableRetainReleasePairing)
1749 return false;
1750 }
1751
1752 return TopDownNestingDetected && BottomUpNestingDetected;
1753}
1754
1755/// Move the calls in RetainsToMove and ReleasesToMove.
1756void ObjCARCOpt::MoveCalls(Value *Arg, RRInfo &RetainsToMove,
1757 RRInfo &ReleasesToMove,
1758 BlotMapVector<Value *, RRInfo> &Retains,
1759 DenseMap<Value *, RRInfo> &Releases,
1760 SmallVectorImpl<Instruction *> &DeadInsts,
1761 Module *M) {
1762 LLVM_DEBUG(dbgs() << "== ObjCARCOpt::MoveCalls ==\n");
1763
1764 // Insert the new retain and release calls.
1765 for (Instruction *InsertPt : ReleasesToMove.ReverseInsertPts) {
1766 Function *Decl = EP.get(kind: ARCRuntimeEntryPointKind::Retain);
1767 SmallVector<OperandBundleDef, 1> BundleList;
1768 addOpBundleForFunclet(BB: InsertPt->getParent(), OpBundles&: BundleList);
1769 CallInst *Call =
1770 CallInst::Create(Func: Decl, Args: Arg, Bundles: BundleList, NameStr: "", InsertBefore: InsertPt->getIterator());
1771 Call->setDoesNotThrow();
1772 Call->setTailCall();
1773
1774 LLVM_DEBUG(dbgs() << "Inserting new Retain: " << *Call
1775 << "\n"
1776 "At insertion point: "
1777 << *InsertPt << "\n");
1778 }
1779 for (Instruction *InsertPt : RetainsToMove.ReverseInsertPts) {
1780 Function *Decl = EP.get(kind: ARCRuntimeEntryPointKind::Release);
1781 SmallVector<OperandBundleDef, 1> BundleList;
1782 addOpBundleForFunclet(BB: InsertPt->getParent(), OpBundles&: BundleList);
1783 CallInst *Call =
1784 CallInst::Create(Func: Decl, Args: Arg, Bundles: BundleList, NameStr: "", InsertBefore: InsertPt->getIterator());
1785 // Attach a clang.imprecise_release metadata tag, if appropriate.
1786 if (MDNode *M = ReleasesToMove.ReleaseMetadata)
1787 Call->setMetadata(KindID: MDKindCache.get(ID: ARCMDKindID::ImpreciseRelease), Node: M);
1788 Call->setDoesNotThrow();
1789 if (ReleasesToMove.IsTailCallRelease)
1790 Call->setTailCall();
1791
1792 LLVM_DEBUG(dbgs() << "Inserting new Release: " << *Call
1793 << "\n"
1794 "At insertion point: "
1795 << *InsertPt << "\n");
1796 }
1797
1798 // Delete the original retain and release calls.
1799 for (Instruction *OrigRetain : RetainsToMove.Calls) {
1800 Retains.blot(Key: OrigRetain);
1801 DeadInsts.push_back(Elt: OrigRetain);
1802 LLVM_DEBUG(dbgs() << "Deleting retain: " << *OrigRetain << "\n");
1803 }
1804 for (Instruction *OrigRelease : ReleasesToMove.Calls) {
1805 Releases.erase(Val: OrigRelease);
1806 DeadInsts.push_back(Elt: OrigRelease);
1807 LLVM_DEBUG(dbgs() << "Deleting release: " << *OrigRelease << "\n");
1808 }
1809}
1810
1811bool ObjCARCOpt::PairUpRetainsAndReleases(
1812 DenseMap<const BasicBlock *, BBState> &BBStates,
1813 BlotMapVector<Value *, RRInfo> &Retains,
1814 DenseMap<Value *, RRInfo> &Releases, Module *M,
1815 Instruction *Retain,
1816 SmallVectorImpl<Instruction *> &DeadInsts, RRInfo &RetainsToMove,
1817 RRInfo &ReleasesToMove, Value *Arg, bool KnownSafe,
1818 bool &AnyPairsCompletelyEliminated) {
1819 // If a pair happens in a region where it is known that the reference count
1820 // is already incremented, we can similarly ignore possible decrements unless
1821 // we are dealing with a retainable object with multiple provenance sources.
1822 bool KnownSafeTD = true, KnownSafeBU = true;
1823 bool CFGHazardAfflicted = false;
1824
1825 // Connect the dots between the top-down-collected RetainsToMove and
1826 // bottom-up-collected ReleasesToMove to form sets of related calls.
1827 // This is an iterative process so that we connect multiple releases
1828 // to multiple retains if needed.
1829 unsigned OldDelta = 0;
1830 unsigned NewDelta = 0;
1831 unsigned OldCount = 0;
1832 unsigned NewCount = 0;
1833 bool FirstRelease = true;
1834 for (SmallVector<Instruction *, 4> NewRetains{Retain};;) {
1835 SmallVector<Instruction *, 4> NewReleases;
1836 for (Instruction *NewRetain : NewRetains) {
1837 auto It = Retains.find(Key: NewRetain);
1838 assert(It != Retains.end());
1839 const RRInfo &NewRetainRRI = It->second;
1840 KnownSafeTD &= NewRetainRRI.KnownSafe;
1841 CFGHazardAfflicted |= NewRetainRRI.CFGHazardAfflicted;
1842 for (Instruction *NewRetainRelease : NewRetainRRI.Calls) {
1843 auto Jt = Releases.find(Val: NewRetainRelease);
1844 if (Jt == Releases.end())
1845 return false;
1846 const RRInfo &NewRetainReleaseRRI = Jt->second;
1847
1848 // If the release does not have a reference to the retain as well,
1849 // something happened which is unaccounted for. Do not do anything.
1850 //
1851 // This can happen if we catch an additive overflow during path count
1852 // merging.
1853 if (!NewRetainReleaseRRI.Calls.count(Ptr: NewRetain))
1854 return false;
1855
1856 if (ReleasesToMove.Calls.insert(Ptr: NewRetainRelease).second) {
1857 // If we overflow when we compute the path count, don't remove/move
1858 // anything.
1859 const BBState &NRRBBState = BBStates[NewRetainRelease->getParent()];
1860 unsigned PathCount = BBState::OverflowOccurredValue;
1861 if (NRRBBState.GetAllPathCountWithOverflow(PathCount))
1862 return false;
1863 assert(PathCount != BBState::OverflowOccurredValue &&
1864 "PathCount at this point can not be "
1865 "OverflowOccurredValue.");
1866 OldDelta -= PathCount;
1867
1868 // Merge the ReleaseMetadata and IsTailCallRelease values.
1869 if (FirstRelease) {
1870 ReleasesToMove.ReleaseMetadata =
1871 NewRetainReleaseRRI.ReleaseMetadata;
1872 ReleasesToMove.IsTailCallRelease =
1873 NewRetainReleaseRRI.IsTailCallRelease;
1874 FirstRelease = false;
1875 } else {
1876 if (ReleasesToMove.ReleaseMetadata !=
1877 NewRetainReleaseRRI.ReleaseMetadata)
1878 ReleasesToMove.ReleaseMetadata = nullptr;
1879 if (ReleasesToMove.IsTailCallRelease !=
1880 NewRetainReleaseRRI.IsTailCallRelease)
1881 ReleasesToMove.IsTailCallRelease = false;
1882 }
1883
1884 // Collect the optimal insertion points.
1885 if (!KnownSafe)
1886 for (Instruction *RIP : NewRetainReleaseRRI.ReverseInsertPts) {
1887 if (ReleasesToMove.ReverseInsertPts.insert(Ptr: RIP).second) {
1888 // If we overflow when we compute the path count, don't
1889 // remove/move anything.
1890 const BBState &RIPBBState = BBStates[RIP->getParent()];
1891 PathCount = BBState::OverflowOccurredValue;
1892 if (RIPBBState.GetAllPathCountWithOverflow(PathCount))
1893 return false;
1894 assert(PathCount != BBState::OverflowOccurredValue &&
1895 "PathCount at this point can not be "
1896 "OverflowOccurredValue.");
1897 NewDelta -= PathCount;
1898 }
1899 }
1900 NewReleases.push_back(Elt: NewRetainRelease);
1901 }
1902 }
1903 }
1904 NewRetains.clear();
1905 if (NewReleases.empty()) break;
1906
1907 // Back the other way.
1908 for (Instruction *NewRelease : NewReleases) {
1909 auto It = Releases.find(Val: NewRelease);
1910 assert(It != Releases.end());
1911 const RRInfo &NewReleaseRRI = It->second;
1912 KnownSafeBU &= NewReleaseRRI.KnownSafe;
1913 CFGHazardAfflicted |= NewReleaseRRI.CFGHazardAfflicted;
1914 for (Instruction *NewReleaseRetain : NewReleaseRRI.Calls) {
1915 auto Jt = Retains.find(Key: NewReleaseRetain);
1916 if (Jt == Retains.end())
1917 return false;
1918 const RRInfo &NewReleaseRetainRRI = Jt->second;
1919
1920 // If the retain does not have a reference to the release as well,
1921 // something happened which is unaccounted for. Do not do anything.
1922 //
1923 // This can happen if we catch an additive overflow during path count
1924 // merging.
1925 if (!NewReleaseRetainRRI.Calls.count(Ptr: NewRelease))
1926 return false;
1927
1928 if (RetainsToMove.Calls.insert(Ptr: NewReleaseRetain).second) {
1929 // If we overflow when we compute the path count, don't remove/move
1930 // anything.
1931 const BBState &NRRBBState = BBStates[NewReleaseRetain->getParent()];
1932 unsigned PathCount = BBState::OverflowOccurredValue;
1933 if (NRRBBState.GetAllPathCountWithOverflow(PathCount))
1934 return false;
1935 assert(PathCount != BBState::OverflowOccurredValue &&
1936 "PathCount at this point can not be "
1937 "OverflowOccurredValue.");
1938 OldDelta += PathCount;
1939 OldCount += PathCount;
1940
1941 // Collect the optimal insertion points.
1942 if (!KnownSafe)
1943 for (Instruction *RIP : NewReleaseRetainRRI.ReverseInsertPts) {
1944 if (RetainsToMove.ReverseInsertPts.insert(Ptr: RIP).second) {
1945 // If we overflow when we compute the path count, don't
1946 // remove/move anything.
1947 const BBState &RIPBBState = BBStates[RIP->getParent()];
1948
1949 PathCount = BBState::OverflowOccurredValue;
1950 if (RIPBBState.GetAllPathCountWithOverflow(PathCount))
1951 return false;
1952 assert(PathCount != BBState::OverflowOccurredValue &&
1953 "PathCount at this point can not be "
1954 "OverflowOccurredValue.");
1955 NewDelta += PathCount;
1956 NewCount += PathCount;
1957 }
1958 }
1959 NewRetains.push_back(Elt: NewReleaseRetain);
1960 }
1961 }
1962 }
1963 if (NewRetains.empty()) break;
1964 }
1965
1966 // We can only remove pointers if we are known safe in both directions.
1967 bool UnconditionallySafe = KnownSafeTD && KnownSafeBU;
1968 if (UnconditionallySafe) {
1969 RetainsToMove.ReverseInsertPts.clear();
1970 ReleasesToMove.ReverseInsertPts.clear();
1971 NewCount = 0;
1972 } else {
1973 // Determine whether the new insertion points we computed preserve the
1974 // balance of retain and release calls through the program.
1975 // TODO: If the fully aggressive solution isn't valid, try to find a
1976 // less aggressive solution which is.
1977 if (NewDelta != 0)
1978 return false;
1979
1980 // At this point, we are not going to remove any RR pairs, but we still are
1981 // able to move RR pairs. If one of our pointers is afflicted with
1982 // CFGHazards, we cannot perform such code motion so exit early.
1983 const bool WillPerformCodeMotion =
1984 !RetainsToMove.ReverseInsertPts.empty() ||
1985 !ReleasesToMove.ReverseInsertPts.empty();
1986 if (CFGHazardAfflicted && WillPerformCodeMotion)
1987 return false;
1988 }
1989
1990 // Determine whether the original call points are balanced in the retain and
1991 // release calls through the program. If not, conservatively don't touch
1992 // them.
1993 // TODO: It's theoretically possible to do code motion in this case, as
1994 // long as the existing imbalances are maintained.
1995 if (OldDelta != 0)
1996 return false;
1997
1998 Changed = true;
1999 assert(OldCount != 0 && "Unreachable code?");
2000 NumRRs += OldCount - NewCount;
2001 // Set to true if we completely removed any RR pairs.
2002 AnyPairsCompletelyEliminated = NewCount == 0;
2003
2004 // We can move calls!
2005 return true;
2006}
2007
2008/// Identify pairings between the retains and releases, and delete and/or move
2009/// them.
2010bool ObjCARCOpt::PerformCodePlacement(
2011 DenseMap<const BasicBlock *, BBState> &BBStates,
2012 BlotMapVector<Value *, RRInfo> &Retains,
2013 DenseMap<Value *, RRInfo> &Releases, Module *M) {
2014 LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::PerformCodePlacement ==\n");
2015
2016 bool AnyPairsCompletelyEliminated = false;
2017 SmallVector<Instruction *, 8> DeadInsts;
2018
2019 // Visit each retain.
2020 for (BlotMapVector<Value *, RRInfo>::const_iterator I = Retains.begin(),
2021 E = Retains.end();
2022 I != E; ++I) {
2023 Value *V = I->first;
2024 if (!V) continue; // blotted
2025
2026 Instruction *Retain = cast<Instruction>(Val: V);
2027
2028 LLVM_DEBUG(dbgs() << "Visiting: " << *Retain << "\n");
2029
2030 Value *Arg = GetArgRCIdentityRoot(Inst: Retain);
2031
2032 // If the object being released is in static or stack storage, we know it's
2033 // not being managed by ObjC reference counting, so we can delete pairs
2034 // regardless of what possible decrements or uses lie between them.
2035 bool KnownSafe = isa<Constant>(Val: Arg) || isa<AllocaInst>(Val: Arg);
2036
2037 // A constant pointer can't be pointing to an object on the heap. It may
2038 // be reference-counted, but it won't be deleted.
2039 if (const LoadInst *LI = dyn_cast<LoadInst>(Val: Arg))
2040 if (const GlobalVariable *GV =
2041 dyn_cast<GlobalVariable>(
2042 Val: GetRCIdentityRoot(V: LI->getPointerOperand())))
2043 if (GV->isConstant())
2044 KnownSafe = true;
2045
2046 // Connect the dots between the top-down-collected RetainsToMove and
2047 // bottom-up-collected ReleasesToMove to form sets of related calls.
2048 RRInfo RetainsToMove, ReleasesToMove;
2049
2050 bool PerformMoveCalls = PairUpRetainsAndReleases(
2051 BBStates, Retains, Releases, M, Retain, DeadInsts,
2052 RetainsToMove, ReleasesToMove, Arg, KnownSafe,
2053 AnyPairsCompletelyEliminated);
2054
2055 if (PerformMoveCalls) {
2056 // Ok, everything checks out and we're all set. Let's move/delete some
2057 // code!
2058 MoveCalls(Arg, RetainsToMove, ReleasesToMove,
2059 Retains, Releases, DeadInsts, M);
2060 }
2061 }
2062
2063 // Now that we're done moving everything, we can delete the newly dead
2064 // instructions, as we no longer need them as insert points.
2065 while (!DeadInsts.empty())
2066 EraseInstruction(CI: DeadInsts.pop_back_val());
2067
2068 return AnyPairsCompletelyEliminated;
2069}
2070
2071/// Weak pointer optimizations.
2072void ObjCARCOpt::OptimizeWeakCalls(Function &F) {
2073 LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeWeakCalls ==\n");
2074
2075 // First, do memdep-style RLE and S2L optimizations. We can't use memdep
2076 // itself because it uses AliasAnalysis and we need to do provenance
2077 // queries instead.
2078 for (inst_iterator I = inst_begin(F: &F), E = inst_end(F: &F); I != E; ) {
2079 Instruction *Inst = &*I++;
2080
2081 LLVM_DEBUG(dbgs() << "Visiting: " << *Inst << "\n");
2082
2083 ARCInstKind Class = GetBasicARCInstKind(V: Inst);
2084 if (Class != ARCInstKind::LoadWeak &&
2085 Class != ARCInstKind::LoadWeakRetained)
2086 continue;
2087
2088 // Delete objc_loadWeak calls with no users.
2089 if (Class == ARCInstKind::LoadWeak && Inst->use_empty()) {
2090 Inst->eraseFromParent();
2091 Changed = true;
2092 continue;
2093 }
2094
2095 // TODO: For now, just look for an earlier available version of this value
2096 // within the same block. Theoretically, we could do memdep-style non-local
2097 // analysis too, but that would want caching. A better approach would be to
2098 // use the technique that EarlyCSE uses.
2099 inst_iterator Current = std::prev(x: I);
2100 BasicBlock *CurrentBB = &*Current.getBasicBlockIterator();
2101 for (BasicBlock::iterator B = CurrentBB->begin(),
2102 J = Current.getInstructionIterator();
2103 J != B; --J) {
2104 Instruction *EarlierInst = &*std::prev(x: J);
2105 ARCInstKind EarlierClass = GetARCInstKind(V: EarlierInst);
2106 switch (EarlierClass) {
2107 case ARCInstKind::LoadWeak:
2108 case ARCInstKind::LoadWeakRetained: {
2109 // If this is loading from the same pointer, replace this load's value
2110 // with that one.
2111 CallInst *Call = cast<CallInst>(Val: Inst);
2112 CallInst *EarlierCall = cast<CallInst>(Val: EarlierInst);
2113 Value *Arg = Call->getArgOperand(i: 0);
2114 Value *EarlierArg = EarlierCall->getArgOperand(i: 0);
2115 switch (PA.getAA()->alias(V1: Arg, V2: EarlierArg)) {
2116 case AliasResult::MustAlias:
2117 Changed = true;
2118 // If the load has a builtin retain, insert a plain retain for it.
2119 if (Class == ARCInstKind::LoadWeakRetained) {
2120 Function *Decl = EP.get(kind: ARCRuntimeEntryPointKind::Retain);
2121 CallInst *CI =
2122 CallInst::Create(Func: Decl, Args: EarlierCall, NameStr: "", InsertBefore: Call->getIterator());
2123 CI->setTailCall();
2124 }
2125 // Zap the fully redundant load.
2126 Call->replaceAllUsesWith(V: EarlierCall);
2127 Call->eraseFromParent();
2128 goto clobbered;
2129 case AliasResult::MayAlias:
2130 case AliasResult::PartialAlias:
2131 goto clobbered;
2132 case AliasResult::NoAlias:
2133 break;
2134 }
2135 break;
2136 }
2137 case ARCInstKind::StoreWeak:
2138 case ARCInstKind::InitWeak: {
2139 // If this is storing to the same pointer and has the same size etc.
2140 // replace this load's value with the stored value.
2141 CallInst *Call = cast<CallInst>(Val: Inst);
2142 CallInst *EarlierCall = cast<CallInst>(Val: EarlierInst);
2143 Value *Arg = Call->getArgOperand(i: 0);
2144 Value *EarlierArg = EarlierCall->getArgOperand(i: 0);
2145 switch (PA.getAA()->alias(V1: Arg, V2: EarlierArg)) {
2146 case AliasResult::MustAlias:
2147 Changed = true;
2148 // If the load has a builtin retain, insert a plain retain for it.
2149 if (Class == ARCInstKind::LoadWeakRetained) {
2150 Function *Decl = EP.get(kind: ARCRuntimeEntryPointKind::Retain);
2151 CallInst *CI =
2152 CallInst::Create(Func: Decl, Args: EarlierCall, NameStr: "", InsertBefore: Call->getIterator());
2153 CI->setTailCall();
2154 }
2155 // Zap the fully redundant load.
2156 Call->replaceAllUsesWith(V: EarlierCall->getArgOperand(i: 1));
2157 Call->eraseFromParent();
2158 goto clobbered;
2159 case AliasResult::MayAlias:
2160 case AliasResult::PartialAlias:
2161 goto clobbered;
2162 case AliasResult::NoAlias:
2163 break;
2164 }
2165 break;
2166 }
2167 case ARCInstKind::MoveWeak:
2168 case ARCInstKind::CopyWeak:
2169 // TOOD: Grab the copied value.
2170 goto clobbered;
2171 case ARCInstKind::AutoreleasepoolPush:
2172 case ARCInstKind::None:
2173 case ARCInstKind::IntrinsicUser:
2174 case ARCInstKind::User:
2175 // Weak pointers are only modified through the weak entry points
2176 // (and arbitrary calls, which could call the weak entry points).
2177 break;
2178 default:
2179 // Anything else could modify the weak pointer.
2180 goto clobbered;
2181 }
2182 }
2183 clobbered:;
2184 }
2185
2186 // Then, for each destroyWeak with an alloca operand, check to see if
2187 // the alloca and all its users can be zapped.
2188 for (Instruction &Inst : llvm::make_early_inc_range(Range: instructions(F))) {
2189 ARCInstKind Class = GetBasicARCInstKind(V: &Inst);
2190 if (Class != ARCInstKind::DestroyWeak)
2191 continue;
2192
2193 CallInst *Call = cast<CallInst>(Val: &Inst);
2194 Value *Arg = Call->getArgOperand(i: 0);
2195 if (AllocaInst *Alloca = dyn_cast<AllocaInst>(Val: Arg)) {
2196 for (User *U : Alloca->users()) {
2197 const Instruction *UserInst = cast<Instruction>(Val: U);
2198 switch (GetBasicARCInstKind(V: UserInst)) {
2199 case ARCInstKind::InitWeak:
2200 case ARCInstKind::StoreWeak:
2201 case ARCInstKind::DestroyWeak:
2202 continue;
2203 default:
2204 goto done;
2205 }
2206 }
2207 Changed = true;
2208 for (User *U : llvm::make_early_inc_range(Range: Alloca->users())) {
2209 CallInst *UserInst = cast<CallInst>(Val: U);
2210 switch (GetBasicARCInstKind(V: UserInst)) {
2211 case ARCInstKind::InitWeak:
2212 case ARCInstKind::StoreWeak:
2213 // These functions return their second argument.
2214 UserInst->replaceAllUsesWith(V: UserInst->getArgOperand(i: 1));
2215 break;
2216 case ARCInstKind::DestroyWeak:
2217 // No return value.
2218 break;
2219 default:
2220 llvm_unreachable("alloca really is used!");
2221 }
2222 UserInst->eraseFromParent();
2223 }
2224 Alloca->eraseFromParent();
2225 done:;
2226 }
2227 }
2228}
2229
2230/// Identify program paths which execute sequences of retains and releases which
2231/// can be eliminated.
2232bool ObjCARCOpt::OptimizeSequences(Function &F) {
2233 // Releases, Retains - These are used to store the results of the main flow
2234 // analysis. These use Value* as the key instead of Instruction* so that the
2235 // map stays valid when we get around to rewriting code and calls get
2236 // replaced by arguments.
2237 DenseMap<Value *, RRInfo> Releases;
2238 BlotMapVector<Value *, RRInfo> Retains;
2239
2240 // This is used during the traversal of the function to track the
2241 // states for each identified object at each block.
2242 DenseMap<const BasicBlock *, BBState> BBStates;
2243
2244 // Analyze the CFG of the function, and all instructions.
2245 bool NestingDetected = Visit(F, BBStates, Retains, Releases);
2246
2247 if (DisableRetainReleasePairing)
2248 return false;
2249
2250 // Transform.
2251 bool AnyPairsCompletelyEliminated = PerformCodePlacement(BBStates, Retains,
2252 Releases,
2253 M: F.getParent());
2254
2255 return AnyPairsCompletelyEliminated && NestingDetected;
2256}
2257
2258/// Check if there is a dependent call earlier that does not have anything in
2259/// between the Retain and the call that can affect the reference count of their
2260/// shared pointer argument. Note that Retain need not be in BB.
2261static CallInst *HasSafePathToPredecessorCall(const Value *Arg,
2262 Instruction *Retain,
2263 ProvenanceAnalysis &PA) {
2264 auto *Call = dyn_cast_or_null<CallInst>(Val: findSingleDependency(
2265 Flavor: CanChangeRetainCount, Arg, StartBB: Retain->getParent(), StartInst: Retain, PA));
2266
2267 // Check that the pointer is the return value of the call.
2268 if (!Call || Arg != Call)
2269 return nullptr;
2270
2271 // Check that the call is a regular call.
2272 ARCInstKind Class = GetBasicARCInstKind(V: Call);
2273 return Class == ARCInstKind::CallOrUser || Class == ARCInstKind::Call
2274 ? Call
2275 : nullptr;
2276}
2277
2278/// Find a dependent retain that precedes the given autorelease for which there
2279/// is nothing in between the two instructions that can affect the ref count of
2280/// Arg.
2281static CallInst *
2282FindPredecessorRetainWithSafePath(const Value *Arg, BasicBlock *BB,
2283 Instruction *Autorelease,
2284 ProvenanceAnalysis &PA) {
2285 auto *Retain = dyn_cast_or_null<CallInst>(
2286 Val: findSingleDependency(Flavor: CanChangeRetainCount, Arg, StartBB: BB, StartInst: Autorelease, PA));
2287
2288 // Check that we found a retain with the same argument.
2289 if (!Retain || !IsRetain(Class: GetBasicARCInstKind(V: Retain)) ||
2290 GetArgRCIdentityRoot(Inst: Retain) != Arg) {
2291 return nullptr;
2292 }
2293
2294 return Retain;
2295}
2296
2297/// Look for an ``autorelease'' instruction dependent on Arg such that there are
2298/// no instructions dependent on Arg that need a positive ref count in between
2299/// the autorelease and the ret.
2300static CallInst *FindPredecessorAutoreleaseWithSafePath(
2301 const Value *Arg, BasicBlock *BB, ReturnInst *Ret, ProvenanceAnalysis &PA) {
2302 auto *Autorelease = dyn_cast_or_null<CallInst>(
2303 Val: findSingleDependency(Flavor: NeedsPositiveRetainCount, Arg, StartBB: BB, StartInst: Ret, PA));
2304
2305 if (!Autorelease)
2306 return nullptr;
2307 ARCInstKind AutoreleaseClass = GetBasicARCInstKind(V: Autorelease);
2308 if (!IsAutorelease(Class: AutoreleaseClass))
2309 return nullptr;
2310 if (GetArgRCIdentityRoot(Inst: Autorelease) != Arg)
2311 return nullptr;
2312
2313 return Autorelease;
2314}
2315
2316/// Look for this pattern:
2317/// \code
2318/// %call = call i8* @something(...)
2319/// %2 = call i8* @objc_retain(i8* %call)
2320/// %3 = call i8* @objc_autorelease(i8* %2)
2321/// ret i8* %3
2322/// \endcode
2323/// And delete the retain and autorelease.
2324void ObjCARCOpt::OptimizeReturns(Function &F) {
2325 if (!F.getReturnType()->isPointerTy())
2326 return;
2327
2328 LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeReturns ==\n");
2329
2330 for (BasicBlock &BB: F) {
2331 ReturnInst *Ret = dyn_cast<ReturnInst>(Val: &BB.back());
2332 if (!Ret)
2333 continue;
2334
2335 LLVM_DEBUG(dbgs() << "Visiting: " << *Ret << "\n");
2336
2337 const Value *Arg = GetRCIdentityRoot(V: Ret->getOperand(i_nocapture: 0));
2338
2339 // Look for an ``autorelease'' instruction that is a predecessor of Ret and
2340 // dependent on Arg such that there are no instructions dependent on Arg
2341 // that need a positive ref count in between the autorelease and Ret.
2342 CallInst *Autorelease =
2343 FindPredecessorAutoreleaseWithSafePath(Arg, BB: &BB, Ret, PA);
2344
2345 if (!Autorelease)
2346 continue;
2347
2348 CallInst *Retain = FindPredecessorRetainWithSafePath(
2349 Arg, BB: Autorelease->getParent(), Autorelease, PA);
2350
2351 if (!Retain)
2352 continue;
2353
2354 // Check that there is nothing that can affect the reference count
2355 // between the retain and the call. Note that Retain need not be in BB.
2356 CallInst *Call = HasSafePathToPredecessorCall(Arg, Retain, PA);
2357
2358 // Don't remove retainRV/autoreleaseRV pairs if the call isn't a tail call.
2359 if (!Call ||
2360 (!Call->isTailCall() &&
2361 GetBasicARCInstKind(V: Retain) == ARCInstKind::RetainRV &&
2362 GetBasicARCInstKind(V: Autorelease) == ARCInstKind::AutoreleaseRV))
2363 continue;
2364
2365 // If so, we can zap the retain and autorelease.
2366 Changed = true;
2367 ++NumRets;
2368 LLVM_DEBUG(dbgs() << "Erasing: " << *Retain << "\nErasing: " << *Autorelease
2369 << "\n");
2370 BundledInsts->eraseInst(CI: Retain);
2371 EraseInstruction(CI: Autorelease);
2372 }
2373}
2374
2375#ifndef NDEBUG
2376void
2377ObjCARCOpt::GatherStatistics(Function &F, bool AfterOptimization) {
2378 Statistic &NumRetains =
2379 AfterOptimization ? NumRetainsAfterOpt : NumRetainsBeforeOpt;
2380 Statistic &NumReleases =
2381 AfterOptimization ? NumReleasesAfterOpt : NumReleasesBeforeOpt;
2382
2383 for (inst_iterator I = inst_begin(&F), E = inst_end(&F); I != E; ) {
2384 Instruction *Inst = &*I++;
2385 switch (GetBasicARCInstKind(Inst)) {
2386 default:
2387 break;
2388 case ARCInstKind::Retain:
2389 ++NumRetains;
2390 break;
2391 case ARCInstKind::Release:
2392 ++NumReleases;
2393 break;
2394 }
2395 }
2396}
2397#endif
2398
2399void ObjCARCOpt::init(Function &F) {
2400 if (!EnableARCOpts)
2401 return;
2402
2403 // Intuitively, objc_retain and others are nocapture, however in practice
2404 // they are not, because they return their argument value. And objc_release
2405 // calls finalizers which can have arbitrary side effects.
2406 MDKindCache.init(Mod: F.getParent());
2407
2408 // Initialize our runtime entry point cache.
2409 EP.init(M: F.getParent());
2410
2411 // Compute which blocks are in which funclet.
2412 if (F.hasPersonalityFn() &&
2413 isScopedEHPersonality(Pers: classifyEHPersonality(Pers: F.getPersonalityFn())))
2414 BlockEHColors = colorEHFunclets(F);
2415}
2416
2417bool ObjCARCOpt::run(Function &F, AAResults &AA) {
2418 if (!EnableARCOpts)
2419 return false;
2420
2421 Changed = CFGChanged = false;
2422 BundledRetainClaimRVs BRV(EP, /*ContractPass=*/false, /*UseClaimRV=*/false);
2423 BundledInsts = &BRV;
2424
2425 LLVM_DEBUG(dbgs() << "<<< ObjCARCOpt: Visiting Function: " << F.getName()
2426 << " >>>"
2427 "\n");
2428
2429 std::pair<bool, bool> R = BundledInsts->insertAfterInvokes(F, DT: nullptr);
2430 Changed |= R.first;
2431 CFGChanged |= R.second;
2432
2433 PA.setAA(&AA);
2434
2435#ifndef NDEBUG
2436 if (AreStatisticsEnabled()) {
2437 GatherStatistics(F, false);
2438 }
2439#endif
2440
2441 // This pass performs several distinct transformations. As a compile-time aid
2442 // when compiling code that isn't ObjC, skip these if the relevant ObjC
2443 // library functions aren't declared.
2444
2445 // Preliminary optimizations. This also computes UsedInThisFunction.
2446 OptimizeIndividualCalls(F);
2447
2448 // Optimizations for weak pointers.
2449 if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::LoadWeak)) |
2450 (1 << unsigned(ARCInstKind::LoadWeakRetained)) |
2451 (1 << unsigned(ARCInstKind::StoreWeak)) |
2452 (1 << unsigned(ARCInstKind::InitWeak)) |
2453 (1 << unsigned(ARCInstKind::CopyWeak)) |
2454 (1 << unsigned(ARCInstKind::MoveWeak)) |
2455 (1 << unsigned(ARCInstKind::DestroyWeak))))
2456 OptimizeWeakCalls(F);
2457
2458 // Optimizations for retain+release pairs.
2459 if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::Retain)) |
2460 (1 << unsigned(ARCInstKind::RetainRV)) |
2461 (1 << unsigned(ARCInstKind::RetainBlock))))
2462 if (UsedInThisFunction & (1 << unsigned(ARCInstKind::Release)))
2463 // Run OptimizeSequences until it either stops making changes or
2464 // no retain+release pair nesting is detected.
2465 while (OptimizeSequences(F)) {}
2466
2467 // Optimizations if objc_autorelease is used.
2468 if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::Autorelease)) |
2469 (1 << unsigned(ARCInstKind::AutoreleaseRV))))
2470 OptimizeReturns(F);
2471
2472 // Optimizations for autorelease pools.
2473 if (UsedInThisFunction & ((1 << unsigned(ARCInstKind::AutoreleasepoolPush)) |
2474 (1 << unsigned(ARCInstKind::AutoreleasepoolPop))))
2475 OptimizeAutoreleasePools(F);
2476
2477 // Gather statistics after optimization.
2478#ifndef NDEBUG
2479 if (AreStatisticsEnabled()) {
2480 GatherStatistics(F, true);
2481 }
2482#endif
2483
2484 LLVM_DEBUG(dbgs() << "\n");
2485
2486 return Changed;
2487}
2488
2489/// Interprocedurally determine if calls made by the given call site can
2490/// possibly produce autoreleases.
2491bool MayAutorelease(const CallBase &CB, unsigned Depth = 0) {
2492 if (CB.onlyReadsMemory())
2493 return false;
2494
2495 // This recursion depth limit is arbitrary. It's just great
2496 // enough to cover known interesting testcases.
2497 if (Depth > 5)
2498 return true;
2499
2500 if (const Function *Callee = CB.getCalledFunction()) {
2501 if (!Callee->hasExactDefinition())
2502 return true;
2503 for (const BasicBlock &BB : *Callee) {
2504 // Track nested autorelease pools in a single pass. Autoreleases inside a
2505 // pool are drained before the pool ends; only effects at function scope
2506 // (empty stack) or in a pool not closed in this block matter.
2507 SmallVector<bool, 4> PoolStack;
2508 for (const Instruction &I : BB) {
2509 ARCInstKind InstKind = GetBasicARCInstKind(V: &I);
2510 switch (InstKind) {
2511 case ARCInstKind::AutoreleasepoolPush:
2512 PoolStack.push_back(Elt: false);
2513 break;
2514
2515 case ARCInstKind::AutoreleasepoolPop:
2516 if (!PoolStack.empty())
2517 PoolStack.pop_back();
2518 break;
2519
2520 case ARCInstKind::Autorelease:
2521 case ARCInstKind::AutoreleaseRV:
2522 case ARCInstKind::FusedRetainAutorelease:
2523 case ARCInstKind::FusedRetainAutoreleaseRV:
2524 case ARCInstKind::LoadWeak:
2525 // These may produce autoreleases
2526 if (PoolStack.empty())
2527 return true;
2528 PoolStack.back() = true;
2529 break;
2530
2531 case ARCInstKind::Retain:
2532 case ARCInstKind::RetainRV:
2533 case ARCInstKind::UnsafeClaimRV:
2534 case ARCInstKind::RetainBlock:
2535 case ARCInstKind::Release:
2536 case ARCInstKind::NoopCast:
2537 case ARCInstKind::LoadWeakRetained:
2538 case ARCInstKind::StoreWeak:
2539 case ARCInstKind::InitWeak:
2540 case ARCInstKind::MoveWeak:
2541 case ARCInstKind::CopyWeak:
2542 case ARCInstKind::DestroyWeak:
2543 case ARCInstKind::StoreStrong:
2544 // These ObjC runtime functions don't produce autoreleases
2545 break;
2546
2547 case ARCInstKind::CallOrUser:
2548 case ARCInstKind::Call:
2549 // For non-ObjC function calls, recursively analyze.
2550 if (MayAutorelease(CB: cast<CallBase>(Val: I), Depth: Depth + 1)) {
2551 if (PoolStack.empty())
2552 return true;
2553 PoolStack.back() = true;
2554 }
2555 break;
2556
2557 case ARCInstKind::IntrinsicUser:
2558 case ARCInstKind::User:
2559 case ARCInstKind::None:
2560 // These are not relevant for autorelease analysis
2561 break;
2562 }
2563 }
2564 if (!PoolStack.empty() && llvm::is_contained(Range&: PoolStack, Element: true))
2565 return true;
2566 }
2567 return false;
2568 }
2569
2570 return true;
2571}
2572
2573/// Optimize autorelease pools by eliminating empty push/pop pairs.
2574void ObjCARCOpt::OptimizeAutoreleasePools(Function &F) {
2575 LLVM_DEBUG(dbgs() << "\n== ObjCARCOpt::OptimizeAutoreleasePools ==\n");
2576
2577 OptimizationRemarkEmitter ORE(&F);
2578
2579 // Process each basic block independently.
2580 // TODO: Can we optimize inter-block autorelease pool pairs?
2581 // This would involve tracking autorelease pool state across blocks.
2582 for (BasicBlock &BB : F) {
2583 // Use a stack to track nested autorelease pools
2584 SmallVector<std::pair<CallInst *, bool>, 4>
2585 PoolStack; // {push_inst, has_autorelease_in_scope}
2586
2587 for (Instruction &Inst : llvm::make_early_inc_range(Range&: BB)) {
2588 ARCInstKind Class = GetBasicARCInstKind(V: &Inst);
2589
2590 switch (Class) {
2591 case ARCInstKind::AutoreleasepoolPush: {
2592 // Start tracking a new autorelease pool scope
2593 auto *Push = cast<CallInst>(Val: &Inst);
2594 PoolStack.push_back(
2595 Elt: {Push, false}); // {push_inst, has_autorelease_in_scope}
2596 LLVM_DEBUG(dbgs() << "Found autorelease pool push: " << *Push << "\n");
2597 break;
2598 }
2599
2600 case ARCInstKind::AutoreleasepoolPop: {
2601 auto *Pop = cast<CallInst>(Val: &Inst);
2602
2603 if (PoolStack.empty())
2604 break;
2605
2606 auto &TopPool = PoolStack.back();
2607 CallInst *PendingPush = TopPool.first;
2608 bool HasAutoreleaseInScope = TopPool.second;
2609
2610 // Pop the stack - remove this pool scope
2611 PoolStack.pop_back();
2612
2613 // Bail if this pop doesn't match the pending push
2614 if (Pop->getArgOperand(i: 0)->stripPointerCasts() != PendingPush)
2615 break;
2616
2617 // Bail if there were autoreleases in this scope
2618 if (HasAutoreleaseInScope)
2619 break;
2620
2621 // Optimize: eliminate this empty autorelease pool pair
2622 ORE.emit(RemarkBuilder: [&]() {
2623 return OptimizationRemark(DEBUG_TYPE, "AutoreleasePoolElimination",
2624 PendingPush)
2625 << "eliminated empty autorelease pool pair";
2626 });
2627
2628 // Replace all uses of push with poison before deletion
2629 PendingPush->replaceAllUsesWith(
2630 V: PoisonValue::get(T: PendingPush->getType()));
2631
2632 Pop->eraseFromParent();
2633 PendingPush->eraseFromParent();
2634
2635 Changed = true;
2636 ++NumNoops;
2637 break;
2638 }
2639 case ARCInstKind::CallOrUser:
2640 case ARCInstKind::Call:
2641 if (!MayAutorelease(CB: cast<CallBase>(Val&: Inst)))
2642 break;
2643 [[fallthrough]];
2644 case ARCInstKind::Autorelease:
2645 case ARCInstKind::AutoreleaseRV:
2646 case ARCInstKind::FusedRetainAutorelease:
2647 case ARCInstKind::FusedRetainAutoreleaseRV:
2648 case ARCInstKind::LoadWeak: {
2649 // Track that we have autorelease calls in the current pool scope
2650 if (!PoolStack.empty()) {
2651 PoolStack.back().second = true; // Set has_autorelease_in_scope = true
2652 LLVM_DEBUG(
2653 dbgs()
2654 << "Found autorelease or potential autorelease in pool scope: "
2655 << Inst << "\n");
2656 }
2657 break;
2658 }
2659
2660 // Enumerate all remaining ARCInstKind cases explicitly
2661 case ARCInstKind::Retain:
2662 case ARCInstKind::RetainRV:
2663 case ARCInstKind::UnsafeClaimRV:
2664 case ARCInstKind::RetainBlock:
2665 case ARCInstKind::Release:
2666 case ARCInstKind::NoopCast:
2667 case ARCInstKind::LoadWeakRetained:
2668 case ARCInstKind::StoreWeak:
2669 case ARCInstKind::InitWeak:
2670 case ARCInstKind::MoveWeak:
2671 case ARCInstKind::CopyWeak:
2672 case ARCInstKind::DestroyWeak:
2673 case ARCInstKind::StoreStrong:
2674 case ARCInstKind::IntrinsicUser:
2675 case ARCInstKind::User:
2676 case ARCInstKind::None:
2677 // These instruction kinds don't affect autorelease pool optimization
2678 break;
2679 }
2680 }
2681 }
2682}
2683
2684/// @}
2685///
2686
2687PreservedAnalyses ObjCARCOptPass::run(Function &F,
2688 FunctionAnalysisManager &AM) {
2689 ObjCARCOpt OCAO;
2690 OCAO.init(F);
2691
2692 bool Changed = OCAO.run(F, AA&: AM.getResult<AAManager>(IR&: F));
2693 bool CFGChanged = OCAO.hasCFGChanged();
2694 if (Changed) {
2695 PreservedAnalyses PA;
2696 if (!CFGChanged)
2697 PA.preserveSet<CFGAnalyses>();
2698 return PA;
2699 }
2700 return PreservedAnalyses::all();
2701}
2702