Coverage Report

Created: 2017-10-03 07:32

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