Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/ObjCARC/DependencyAnalysis.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- DependencyAnalysis.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
/// \file
9
///
10
/// This file defines special dependency analysis routines used in Objective C
11
/// ARC Optimizations.
12
///
13
/// WARNING: This file knows about certain library functions. It recognizes them
14
/// by name, and hardwires knowledge of their semantics.
15
///
16
/// WARNING: This file knows about how certain Objective-C library functions are
17
/// used. Naive LLVM IR transformations which would otherwise be
18
/// behavior-preserving may break these assumptions.
19
///
20
//===----------------------------------------------------------------------===//
21
22
#include "DependencyAnalysis.h"
23
#include "ObjCARC.h"
24
#include "ProvenanceAnalysis.h"
25
#include "llvm/IR/CFG.h"
26
27
using namespace llvm;
28
using namespace llvm::objcarc;
29
30
#define DEBUG_TYPE "objc-arc-dependency"
31
32
/// Test whether the given instruction can result in a reference count
33
/// modification (positive or negative) for the pointer's object.
34
bool llvm::objcarc::CanAlterRefCount(const Instruction *Inst, const Value *Ptr,
35
                                     ProvenanceAnalysis &PA,
36
4.67k
                                     ARCInstKind Class) {
37
4.67k
  switch (Class) {
38
4.67k
  case ARCInstKind::Autorelease:
39
1.83k
  case ARCInstKind::AutoreleaseRV:
40
1.83k
  case ARCInstKind::IntrinsicUser:
41
1.83k
  case ARCInstKind::User:
42
1.83k
    // These operations never directly modify a reference count.
43
1.83k
    return false;
44
2.84k
  default: break;
45
2.84k
  }
46
2.84k
47
2.84k
  const auto *Call = cast<CallBase>(Inst);
48
2.84k
49
2.84k
  // See if AliasAnalysis can help us with the call.
50
2.84k
  FunctionModRefBehavior MRB = PA.getAA()->getModRefBehavior(Call);
51
2.84k
  if (AliasAnalysis::onlyReadsMemory(MRB))
52
0
    return false;
53
2.84k
  if (AliasAnalysis::onlyAccessesArgPointees(MRB)) {
54
0
    const DataLayout &DL = Inst->getModule()->getDataLayout();
55
0
    for (const Value *Op : Call->args()) {
56
0
      if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) &&
57
0
          PA.related(Ptr, Op, DL))
58
0
        return true;
59
0
    }
60
0
    return false;
61
2.84k
  }
62
2.84k
63
2.84k
  // Assume the worst.
64
2.84k
  return true;
65
2.84k
}
66
67
bool llvm::objcarc::CanDecrementRefCount(const Instruction *Inst,
68
                                         const Value *Ptr,
69
                                         ProvenanceAnalysis &PA,
70
39
                                         ARCInstKind Class) {
71
39
  // First perform a quick check if Class can not touch ref counts.
72
39
  if (!CanDecrementRefCount(Class))
73
32
    return false;
74
7
75
7
  // Otherwise, just use CanAlterRefCount for now.
76
7
  return CanAlterRefCount(Inst, Ptr, PA, Class);
77
7
}
78
79
/// Test whether the given instruction can "use" the given pointer's object in a
80
/// way that requires the reference count to be positive.
81
bool llvm::objcarc::CanUse(const Instruction *Inst, const Value *Ptr,
82
1.06k
                           ProvenanceAnalysis &PA, ARCInstKind Class) {
83
1.06k
  // ARCInstKind::Call operations (as opposed to
84
1.06k
  // ARCInstKind::CallOrUser) never "use" objc pointers.
85
1.06k
  if (Class == ARCInstKind::Call)
86
66
    return false;
87
999
88
999
  const DataLayout &DL = Inst->getModule()->getDataLayout();
89
999
90
999
  // Consider various instructions which may have pointer arguments which are
91
999
  // not "uses".
92
999
  if (const ICmpInst *ICI = dyn_cast<ICmpInst>(Inst)) {
93
8
    // Comparing a pointer with null, or any other constant, isn't really a use,
94
8
    // because we don't care what the pointer points to, or about the values
95
8
    // of any other dynamic reference-counted pointers.
96
8
    if (!IsPotentialRetainableObjPtr(ICI->getOperand(1), *PA.getAA()))
97
0
      return false;
98
991
  } else if (auto CS = ImmutableCallSite(Inst)) {
99
721
    // For calls, just check the arguments (and not the callee operand).
100
721
    for (ImmutableCallSite::arg_iterator OI = CS.arg_begin(),
101
1.37k
         OE = CS.arg_end(); OI != OE; 
++OI657
) {
102
1.00k
      const Value *Op = *OI;
103
1.00k
      if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) &&
104
1.00k
          
PA.related(Ptr, Op, DL)887
)
105
352
        return true;
106
1.00k
    }
107
721
    
return false369
;
108
270
  } else if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
109
120
    // Special-case stores, because we don't care about the stored value, just
110
120
    // the store address.
111
120
    const Value *Op = GetUnderlyingObjCPtr(SI->getPointerOperand(), DL);
112
120
    // If we can't tell what the underlying object was, assume there is a
113
120
    // dependence.
114
120
    return IsPotentialRetainableObjPtr(Op, *PA.getAA()) &&
115
120
           
PA.related(Op, Ptr, DL)82
;
116
120
  }
117
158
118
158
  // Check each operand for a match.
119
158
  for (User::const_op_iterator OI = Inst->op_begin(), OE = Inst->op_end();
120
290
       OI != OE; 
++OI132
) {
121
158
    const Value *Op = *OI;
122
158
    if (IsPotentialRetainableObjPtr(Op, *PA.getAA()) && PA.related(Ptr, Op, DL))
123
26
      return true;
124
158
  }
125
158
  
return false132
;
126
158
}
127
128
/// Test if there can be dependencies on Inst through Arg. This function only
129
/// tests dependencies relevant for removing pairs of calls.
130
bool
131
llvm::objcarc::Depends(DependenceKind Flavor, Instruction *Inst,
132
160
                       const Value *Arg, ProvenanceAnalysis &PA) {
133
160
  // If we've reached the definition of Arg, stop.
134
160
  if (Inst == Arg)
135
22
    return true;
136
138
137
138
  switch (Flavor) {
138
138
  case NeedsPositiveRetainCount: {
139
47
    ARCInstKind Class = GetARCInstKind(Inst);
140
47
    switch (Class) {
141
47
    case ARCInstKind::AutoreleasepoolPop:
142
10
    case ARCInstKind::AutoreleasepoolPush:
143
10
    case ARCInstKind::None:
144
10
      return false;
145
37
    default:
146
37
      return CanUse(Inst, Arg, PA, Class);
147
0
    }
148
0
  }
149
0
150
8
  case AutoreleasePoolBoundary: {
151
8
    ARCInstKind Class = GetARCInstKind(Inst);
152
8
    switch (Class) {
153
8
    case ARCInstKind::AutoreleasepoolPop:
154
1
    case ARCInstKind::AutoreleasepoolPush:
155
1
      // These mark the end and begin of an autorelease pool scope.
156
1
      return true;
157
7
    default:
158
7
      // Nothing else does this.
159
7
      return false;
160
0
    }
161
0
  }
162
0
163
27
  case CanChangeRetainCount: {
164
27
    ARCInstKind Class = GetARCInstKind(Inst);
165
27
    switch (Class) {
166
27
    case ARCInstKind::AutoreleasepoolPop:
167
1
      // Conservatively assume this can decrement any count.
168
1
      return true;
169
27
    case ARCInstKind::AutoreleasepoolPush:
170
8
    case ARCInstKind::None:
171
8
      return false;
172
18
    default:
173
18
      return CanAlterRefCount(Inst, Arg, PA, Class);
174
0
    }
175
0
  }
176
0
177
49
  case RetainAutoreleaseDep:
178
49
    switch (GetBasicARCInstKind(Inst)) {
179
49
    case ARCInstKind::AutoreleasepoolPop:
180
0
    case ARCInstKind::AutoreleasepoolPush:
181
0
      // Don't merge an objc_autorelease with an objc_retain inside a different
182
0
      // autoreleasepool scope.
183
0
      return true;
184
7
    case ARCInstKind::Retain:
185
7
    case ARCInstKind::RetainRV:
186
7
      // Check for a retain of the same pointer for merging.
187
7
      return GetArgRCIdentityRoot(Inst) == Arg;
188
42
    default:
189
42
      // Nothing else matters for objc_retainAutorelease formation.
190
42
      return false;
191
0
    }
192
0
193
7
  case RetainAutoreleaseRVDep: {
194
7
    ARCInstKind Class = GetBasicARCInstKind(Inst);
195
7
    switch (Class) {
196
7
    case ARCInstKind::Retain:
197
3
    case ARCInstKind::RetainRV:
198
3
      // Check for a retain of the same pointer for merging.
199
3
      return GetArgRCIdentityRoot(Inst) == Arg;
200
4
    default:
201
4
      // Anything that can autorelease interrupts
202
4
      // retainAutoreleaseReturnValue formation.
203
4
      return CanInterruptRV(Class);
204
0
    }
205
0
  }
206
0
207
0
  case RetainRVDep:
208
0
    return CanInterruptRV(GetBasicARCInstKind(Inst));
209
0
  }
210
0
211
0
  llvm_unreachable("Invalid dependence flavor");
212
0
}
213
214
/// Walk up the CFG from StartPos (which is in StartBB) and find local and
215
/// non-local dependencies on Arg.
216
///
217
/// TODO: Cache results?
218
void
219
llvm::objcarc::FindDependencies(DependenceKind Flavor,
220
                                const Value *Arg,
221
                                BasicBlock *StartBB, Instruction *StartInst,
222
                                SmallPtrSetImpl<Instruction *> &DependingInsts,
223
                                SmallPtrSetImpl<const BasicBlock *> &Visited,
224
95
                                ProvenanceAnalysis &PA) {
225
95
  BasicBlock::iterator StartPos = StartInst->getIterator();
226
95
227
95
  SmallVector<std::pair<BasicBlock *, BasicBlock::iterator>, 4> Worklist;
228
95
  Worklist.push_back(std::make_pair(StartBB, StartPos));
229
112
  do {
230
112
    std::pair<BasicBlock *, BasicBlock::iterator> Pair =
231
112
      Worklist.pop_back_val();
232
112
    BasicBlock *LocalStartBB = Pair.first;
233
112
    BasicBlock::iterator LocalStartPos = Pair.second;
234
112
    BasicBlock::iterator StartBBBegin = LocalStartBB->begin();
235
191
    for (;;) {
236
191
      if (LocalStartPos == StartBBBegin) {
237
31
        pred_iterator PI(LocalStartBB), PE(LocalStartBB, false);
238
31
        if (PI == PE)
239
14
          // If we've reached the function entry, produce a null dependence.
240
14
          DependingInsts.insert(nullptr);
241
17
        else
242
17
          // Add the predecessors to the worklist.
243
22
          
do 17
{
244
22
            BasicBlock *PredBB = *PI;
245
22
            if (Visited.insert(PredBB).second)
246
17
              Worklist.push_back(std::make_pair(PredBB, PredBB->end()));
247
22
          } while (++PI != PE);
248
31
        break;
249
31
      }
250
160
251
160
      Instruction *Inst = &*--LocalStartPos;
252
160
      if (Depends(Flavor, Inst, Arg, PA)) {
253
81
        DependingInsts.insert(Inst);
254
81
        break;
255
81
      }
256
160
    }
257
112
  } while (!Worklist.empty());
258
95
259
95
  // Determine whether the original StartBB post-dominates all of the blocks we
260
95
  // visited. If not, insert a sentinal indicating that most optimizations are
261
95
  // not safe.
262
95
  for (const BasicBlock *BB : Visited) {
263
17
    if (BB == StartBB)
264
0
      continue;
265
17
    for (const BasicBlock *Succ : successors(BB))
266
26
      if (Succ != StartBB && 
!Visited.count(Succ)12
) {
267
7
        DependingInsts.insert(reinterpret_cast<Instruction *>(-1));
268
7
        return;
269
7
      }
270
17
  }
271
95
}