Coverage Report

Created: 2019-07-24 05:18

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