Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/ObjCARC/PtrState.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- PtrState.cpp -------------------------------------------------------===//
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
#include "PtrState.h"
10
#include "DependencyAnalysis.h"
11
#include "ObjCARC.h"
12
#include "llvm/Analysis/ObjCARCAnalysisUtils.h"
13
#include "llvm/Analysis/ObjCARCInstKind.h"
14
#include "llvm/IR/BasicBlock.h"
15
#include "llvm/IR/Instruction.h"
16
#include "llvm/IR/Instructions.h"
17
#include "llvm/IR/Value.h"
18
#include "llvm/Support/Casting.h"
19
#include "llvm/Support/Compiler.h"
20
#include "llvm/Support/Debug.h"
21
#include "llvm/Support/ErrorHandling.h"
22
#include "llvm/Support/raw_ostream.h"
23
#include <cassert>
24
#include <iterator>
25
#include <utility>
26
27
using namespace llvm;
28
using namespace llvm::objcarc;
29
30
#define DEBUG_TYPE "objc-arc-ptr-state"
31
32
//===----------------------------------------------------------------------===//
33
//                                  Utility
34
//===----------------------------------------------------------------------===//
35
36
0
raw_ostream &llvm::objcarc::operator<<(raw_ostream &OS, const Sequence S) {
37
0
  switch (S) {
38
0
  case S_None:
39
0
    return OS << "S_None";
40
0
  case S_Retain:
41
0
    return OS << "S_Retain";
42
0
  case S_CanRelease:
43
0
    return OS << "S_CanRelease";
44
0
  case S_Use:
45
0
    return OS << "S_Use";
46
0
  case S_Release:
47
0
    return OS << "S_Release";
48
0
  case S_MovableRelease:
49
0
    return OS << "S_MovableRelease";
50
0
  case S_Stop:
51
0
    return OS << "S_Stop";
52
0
  }
53
0
  llvm_unreachable("Unknown sequence type.");
54
0
}
55
56
//===----------------------------------------------------------------------===//
57
//                                  Sequence
58
//===----------------------------------------------------------------------===//
59
60
1.07k
static Sequence MergeSeqs(Sequence A, Sequence B, bool TopDown) {
61
1.07k
  // The easy cases.
62
1.07k
  if (A == B)
63
841
    return A;
64
231
  if (A == S_None || 
B == S_None207
)
65
99
    return S_None;
66
132
67
132
  if (A > B)
68
69
    std::swap(A, B);
69
132
  if (TopDown) {
70
56
    // Choose the side which is further along in the sequence.
71
56
    if ((A == S_Retain || 
A == S_CanRelease28
) &&
72
56
        (B == S_CanRelease || 
B == S_Use42
))
73
56
      return B;
74
76
  } else {
75
76
    // Choose the side which is further along in the sequence.
76
76
    if ((A == S_Use || 
A == S_CanRelease63
) &&
77
76
        
(68
B == S_Use68
||
B == S_Release49
||
B == S_Stop24
||
B == S_MovableRelease23
))
78
68
      return A;
79
8
    // If both sides are releases, choose the more conservative one.
80
8
    if (A == S_Stop && 
(2
B == S_Release2
||
B == S_MovableRelease0
))
81
2
      return A;
82
6
    if (A == S_Release && B == S_MovableRelease)
83
6
      return A;
84
0
  }
85
0
86
0
  return S_None;
87
0
}
88
89
//===----------------------------------------------------------------------===//
90
//                                   RRInfo
91
//===----------------------------------------------------------------------===//
92
93
1.91k
void RRInfo::clear() {
94
1.91k
  KnownSafe = false;
95
1.91k
  IsTailCallRelease = false;
96
1.91k
  ReleaseMetadata = nullptr;
97
1.91k
  Calls.clear();
98
1.91k
  ReverseInsertPts.clear();
99
1.91k
  CFGHazardAfflicted = false;
100
1.91k
}
101
102
353
bool RRInfo::Merge(const RRInfo &Other) {
103
353
  // Conservatively merge the ReleaseMetadata information.
104
353
  if (ReleaseMetadata != Other.ReleaseMetadata)
105
8
    ReleaseMetadata = nullptr;
106
353
107
353
  // Conservatively merge the boolean state.
108
353
  KnownSafe &= Other.KnownSafe;
109
353
  IsTailCallRelease &= Other.IsTailCallRelease;
110
353
  CFGHazardAfflicted |= Other.CFGHazardAfflicted;
111
353
112
353
  // Merge the call sets.
113
353
  Calls.insert(Other.Calls.begin(), Other.Calls.end());
114
353
115
353
  // Merge the insert point sets. If there are any differences,
116
353
  // that makes this a partial merge.
117
353
  bool Partial = ReverseInsertPts.size() != Other.ReverseInsertPts.size();
118
353
  for (Instruction *Inst : Other.ReverseInsertPts)
119
167
    Partial |= ReverseInsertPts.insert(Inst).second;
120
353
  return Partial;
121
353
}
122
123
//===----------------------------------------------------------------------===//
124
//                                  PtrState
125
//===----------------------------------------------------------------------===//
126
127
1.08k
void PtrState::SetKnownPositiveRefCount() {
128
1.08k
  LLVM_DEBUG(dbgs() << "        Setting Known Positive.\n");
129
1.08k
  KnownPositiveRefCount = true;
130
1.08k
}
131
132
1.55k
void PtrState::ClearKnownPositiveRefCount() {
133
1.55k
  LLVM_DEBUG(dbgs() << "        Clearing Known Positive.\n");
134
1.55k
  KnownPositiveRefCount = false;
135
1.55k
}
136
137
2.02k
void PtrState::SetSeq(Sequence NewSeq) {
138
2.02k
  LLVM_DEBUG(dbgs() << "            Old: " << GetSeq() << "; New: " << NewSeq
139
2.02k
                    << "\n");
140
2.02k
  Seq = NewSeq;
141
2.02k
}
142
143
1.20k
void PtrState::ResetSequenceProgress(Sequence NewSeq) {
144
1.20k
  LLVM_DEBUG(dbgs() << "        Resetting sequence progress.\n");
145
1.20k
  SetSeq(NewSeq);
146
1.20k
  Partial = false;
147
1.20k
  RRI.clear();
148
1.20k
}
149
150
1.07k
void PtrState::Merge(const PtrState &Other, bool TopDown) {
151
1.07k
  Seq = MergeSeqs(GetSeq(), Other.GetSeq(), TopDown);
152
1.07k
  KnownPositiveRefCount &= Other.KnownPositiveRefCount;
153
1.07k
154
1.07k
  // If we're not in a sequence (anymore), drop all associated state.
155
1.07k
  if (Seq == S_None) {
156
702
    Partial = false;
157
702
    RRI.clear();
158
702
  } else 
if (370
Partial370
||
Other.Partial357
) {
159
17
    // If we're doing a merge on a path that's previously seen a partial
160
17
    // merge, conservatively drop the sequence, to avoid doing partial
161
17
    // RR elimination. If the branch predicates for the two merge differ,
162
17
    // mixing them is unsafe.
163
17
    ClearSequenceProgress();
164
353
  } else {
165
353
    // Otherwise merge the other PtrState's RRInfo into our RRInfo. At this
166
353
    // point, we know that currently we are not partial. Stash whether or not
167
353
    // the merge operation caused us to undergo a partial merging of reverse
168
353
    // insertion points.
169
353
    Partial = RRI.Merge(Other.RRI);
170
353
  }
171
1.07k
}
172
173
//===----------------------------------------------------------------------===//
174
//                              BottomUpPtrState
175
//===----------------------------------------------------------------------===//
176
177
391
bool BottomUpPtrState::InitBottomUp(ARCMDKindCache &Cache, Instruction *I) {
178
391
  // If we see two releases in a row on the same pointer. If so, make
179
391
  // a note, and we'll cicle back to revisit it after we've
180
391
  // hopefully eliminated the second release, which may allow us to
181
391
  // eliminate the first release too.
182
391
  // Theoretically we could implement removal of nested retain+release
183
391
  // pairs by making PtrState hold a stack of states, but this is
184
391
  // simple and avoids adding overhead for the non-nested case.
185
391
  bool NestingDetected = false;
186
391
  if (GetSeq() == S_Release || 
GetSeq() == S_MovableRelease388
) {
187
32
    LLVM_DEBUG(
188
32
        dbgs() << "        Found nested releases (i.e. a release pair)\n");
189
32
    NestingDetected = true;
190
32
  }
191
391
192
391
  MDNode *ReleaseMetadata =
193
391
      I->getMetadata(Cache.get(ARCMDKindID::ImpreciseRelease));
194
391
  Sequence NewSeq = ReleaseMetadata ? 
S_MovableRelease249
:
S_Release142
;
195
391
  ResetSequenceProgress(NewSeq);
196
391
  SetReleaseMetadata(ReleaseMetadata);
197
391
  SetKnownSafe(HasKnownPositiveRefCount());
198
391
  SetTailCallRelease(cast<CallInst>(I)->isTailCall());
199
391
  InsertCall(I);
200
391
  SetKnownPositiveRefCount();
201
391
  return NestingDetected;
202
391
}
203
204
346
bool BottomUpPtrState::MatchWithRetain() {
205
346
  SetKnownPositiveRefCount();
206
346
207
346
  Sequence OldSeq = GetSeq();
208
346
  switch (OldSeq) {
209
346
  case S_Stop:
210
90
  case S_Release:
211
90
  case S_MovableRelease:
212
90
  case S_Use:
213
90
    // If OldSeq is not S_Use or OldSeq is S_Use and we are tracking an
214
90
    // imprecise release, clear our reverse insertion points.
215
90
    if (OldSeq != S_Use || 
IsTrackingImpreciseReleases()44
)
216
72
      ClearReverseInsertPts();
217
90
    LLVM_FALLTHROUGH;
218
213
  case S_CanRelease:
219
213
    return true;
220
133
  case S_None:
221
133
    return false;
222
90
  case S_Retain:
223
0
    llvm_unreachable("bottom-up pointer in retain state!");
224
0
  }
225
0
  llvm_unreachable("Sequence unknown enum value");
226
0
}
227
228
bool BottomUpPtrState::HandlePotentialAlterRefCount(Instruction *Inst,
229
                                                    const Value *Ptr,
230
                                                    ProvenanceAnalysis &PA,
231
2.82k
                                                    ARCInstKind Class) {
232
2.82k
  Sequence S = GetSeq();
233
2.82k
234
2.82k
  // Check for possible releases.
235
2.82k
  if (!CanAlterRefCount(Inst, Ptr, PA, Class))
236
1.14k
    return false;
237
1.68k
238
1.68k
  LLVM_DEBUG(dbgs() << "            CanAlterRefCount: Seq: " << S << "; "
239
1.68k
                    << *Ptr << "\n");
240
1.68k
  switch (S) {
241
1.68k
  case S_Use:
242
192
    SetSeq(S_CanRelease);
243
192
    return true;
244
1.68k
  case S_CanRelease:
245
1.48k
  case S_Release:
246
1.48k
  case S_MovableRelease:
247
1.48k
  case S_Stop:
248
1.48k
  case S_None:
249
1.48k
    return false;
250
1.48k
  case S_Retain:
251
0
    llvm_unreachable("bottom-up pointer in retain state!");
252
0
  }
253
0
  llvm_unreachable("Sequence unknown enum value");
254
0
}
255
256
void BottomUpPtrState::HandlePotentialUse(BasicBlock *BB, Instruction *Inst,
257
                                          const Value *Ptr,
258
                                          ProvenanceAnalysis &PA,
259
2.63k
                                          ARCInstKind Class) {
260
2.63k
  auto SetSeqAndInsertReverseInsertPt = [&](Sequence NewSeq){
261
294
    assert(!HasReverseInsertPts());
262
294
    SetSeq(NewSeq);
263
294
    // If this is an invoke instruction, we're scanning it as part of
264
294
    // one of its successor blocks, since we can't insert code after it
265
294
    // in its own block, and we don't want to split critical edges.
266
294
    BasicBlock::iterator InsertAfter;
267
294
    if (isa<InvokeInst>(Inst)) {
268
36
      const auto IP = BB->getFirstInsertionPt();
269
36
      InsertAfter = IP == BB->end() ? 
std::prev(BB->end())3
:
IP33
;
270
36
      if (isa<CatchSwitchInst>(InsertAfter))
271
3
        // A catchswitch must be the only non-phi instruction in its basic
272
3
        // block, so attempting to insert an instruction into such a block would
273
3
        // produce invalid IR.
274
3
        SetCFGHazardAfflicted(true);
275
258
    } else {
276
258
      InsertAfter = std::next(Inst->getIterator());
277
258
    }
278
294
    InsertReverseInsertPt(&*InsertAfter);
279
294
  };
280
2.63k
281
2.63k
  // Check for possible direct uses.
282
2.63k
  switch (GetSeq()) {
283
2.63k
  case S_Release:
284
644
  case S_MovableRelease:
285
644
    if (CanUse(Inst, Ptr, PA, Class)) {
286
272
      LLVM_DEBUG(dbgs() << "            CanUse: Seq: " << GetSeq() << "; "
287
272
                        << *Ptr << "\n");
288
272
      SetSeqAndInsertReverseInsertPt(S_Use);
289
372
    } else if (Seq == S_Release && 
IsUser(Class)47
) {
290
16
      LLVM_DEBUG(dbgs() << "            PreciseReleaseUse: Seq: " << GetSeq()
291
16
                        << "; " << *Ptr << "\n");
292
16
      // Non-movable releases depend on any possible objc pointer use.
293
16
      SetSeqAndInsertReverseInsertPt(S_Stop);
294
356
    } else if (const auto *Call = getreturnRVOperand(*Inst, Class)) {
295
6
      if (CanUse(Call, Ptr, PA, GetBasicARCInstKind(Call))) {
296
6
        LLVM_DEBUG(dbgs() << "            ReleaseUse: Seq: " << GetSeq() << "; "
297
6
                          << *Ptr << "\n");
298
6
        SetSeqAndInsertReverseInsertPt(S_Stop);
299
6
      }
300
6
    }
301
644
    break;
302
644
  case S_Stop:
303
20
    if (CanUse(Inst, Ptr, PA, Class)) {
304
11
      LLVM_DEBUG(dbgs() << "            PreciseStopUse: Seq: " << GetSeq()
305
11
                        << "; " << *Ptr << "\n");
306
11
      SetSeq(S_Use);
307
11
    }
308
20
    break;
309
1.96k
  case S_CanRelease:
310
1.96k
  case S_Use:
311
1.96k
  case S_None:
312
1.96k
    break;
313
1.96k
  case S_Retain:
314
0
    llvm_unreachable("bottom-up pointer in retain state!");
315
2.63k
  }
316
2.63k
}
317
318
//===----------------------------------------------------------------------===//
319
//                              TopDownPtrState
320
//===----------------------------------------------------------------------===//
321
322
346
bool TopDownPtrState::InitTopDown(ARCInstKind Kind, Instruction *I) {
323
346
  bool NestingDetected = false;
324
346
  // Don't do retain+release tracking for ARCInstKind::RetainRV, because
325
346
  // it's
326
346
  // better to let it remain as the first instruction after a call.
327
346
  if (Kind != ARCInstKind::RetainRV) {
328
315
    // If we see two retains in a row on the same pointer. If so, make
329
315
    // a note, and we'll cicle back to revisit it after we've
330
315
    // hopefully eliminated the second retain, which may allow us to
331
315
    // eliminate the first retain too.
332
315
    // Theoretically we could implement removal of nested retain+release
333
315
    // pairs by making PtrState hold a stack of states, but this is
334
315
    // simple and avoids adding overhead for the non-nested case.
335
315
    if (GetSeq() == S_Retain)
336
51
      NestingDetected = true;
337
315
338
315
    ResetSequenceProgress(S_Retain);
339
315
    SetKnownSafe(HasKnownPositiveRefCount());
340
315
    InsertCall(I);
341
315
  }
342
346
343
346
  SetKnownPositiveRefCount();
344
346
  return NestingDetected;
345
346
}
346
347
bool TopDownPtrState::MatchWithRelease(ARCMDKindCache &Cache,
348
389
                                       Instruction *Release) {
349
389
  ClearKnownPositiveRefCount();
350
389
351
389
  Sequence OldSeq = GetSeq();
352
389
353
389
  MDNode *ReleaseMetadata =
354
389
      Release->getMetadata(Cache.get(ARCMDKindID::ImpreciseRelease));
355
389
356
389
  switch (OldSeq) {
357
389
  case S_Retain:
358
82
  case S_CanRelease:
359
82
    if (OldSeq == S_Retain || 
ReleaseMetadata != nullptr45
)
360
65
      ClearReverseInsertPts();
361
82
    LLVM_FALLTHROUGH;
362
197
  case S_Use:
363
197
    SetReleaseMetadata(ReleaseMetadata);
364
197
    SetTailCallRelease(cast<CallInst>(Release)->isTailCall());
365
197
    return true;
366
192
  case S_None:
367
192
    return false;
368
82
  case S_Stop:
369
0
  case S_Release:
370
0
  case S_MovableRelease:
371
0
    llvm_unreachable("top-down pointer in bottom up state!");
372
0
  }
373
0
  llvm_unreachable("Sequence unknown enum value");
374
0
}
375
376
bool TopDownPtrState::HandlePotentialAlterRefCount(Instruction *Inst,
377
                                                   const Value *Ptr,
378
                                                   ProvenanceAnalysis &PA,
379
1.82k
                                                   ARCInstKind Class) {
380
1.82k
  // Check for possible releases. Treat clang.arc.use as a releasing instruction
381
1.82k
  // to prevent sinking a retain past it.
382
1.82k
  if (!CanAlterRefCount(Inst, Ptr, PA, Class) &&
383
1.82k
      
Class != ARCInstKind::IntrinsicUser689
)
384
665
    return false;
385
1.16k
386
1.16k
  LLVM_DEBUG(dbgs() << "            CanAlterRefCount: Seq: " << GetSeq() << "; "
387
1.16k
                    << *Ptr << "\n");
388
1.16k
  ClearKnownPositiveRefCount();
389
1.16k
  switch (GetSeq()) {
390
1.16k
  case S_Retain:
391
192
    SetSeq(S_CanRelease);
392
192
    assert(!HasReverseInsertPts());
393
192
    InsertReverseInsertPt(Inst);
394
192
395
192
    // One call can't cause a transition from S_Retain to S_CanRelease
396
192
    // and S_CanRelease to S_Use. If we've made the first transition,
397
192
    // we're done.
398
192
    return true;
399
1.16k
  case S_Use:
400
970
  case S_CanRelease:
401
970
  case S_None:
402
970
    return false;
403
970
  case S_Stop:
404
0
  case S_Release:
405
0
  case S_MovableRelease:
406
0
    llvm_unreachable("top-down pointer in release state!");
407
0
  }
408
0
  llvm_unreachable("covered switch is not covered!?");
409
0
}
410
411
void TopDownPtrState::HandlePotentialUse(Instruction *Inst, const Value *Ptr,
412
                                         ProvenanceAnalysis &PA,
413
1.63k
                                         ARCInstKind Class) {
414
1.63k
  // Check for possible direct uses.
415
1.63k
  switch (GetSeq()) {
416
1.63k
  case S_CanRelease:
417
356
    if (!CanUse(Inst, Ptr, PA, Class))
418
228
      return;
419
128
    LLVM_DEBUG(dbgs() << "             CanUse: Seq: " << GetSeq() << "; "
420
128
                      << *Ptr << "\n");
421
128
    SetSeq(S_Use);
422
128
    return;
423
1.27k
  case S_Retain:
424
1.27k
  case S_Use:
425
1.27k
  case S_None:
426
1.27k
    return;
427
1.27k
  case S_Stop:
428
0
  case S_Release:
429
0
  case S_MovableRelease:
430
0
    llvm_unreachable("top-down pointer in release state!");
431
1.63k
  }
432
1.63k
}