Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Transforms/ObjCARC/ProvenanceAnalysis.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- ProvenanceAnalysis.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
///
11
/// This file defines a special form of Alias Analysis called ``Provenance
12
/// Analysis''. The word ``provenance'' refers to the history of the ownership
13
/// of an object. Thus ``Provenance Analysis'' is an analysis which attempts to
14
/// use various techniques to determine if locally
15
///
16
/// WARNING: This file knows about certain library functions. It recognizes them
17
/// by name, and hardwires knowledge of their semantics.
18
///
19
/// WARNING: This file knows about how certain Objective-C library functions are
20
/// used. Naive LLVM IR transformations which would otherwise be
21
/// behavior-preserving may break these assumptions.
22
//
23
//===----------------------------------------------------------------------===//
24
25
#include "ProvenanceAnalysis.h"
26
#include "llvm/ADT/SmallPtrSet.h"
27
#include "llvm/ADT/SmallVector.h"
28
#include "llvm/Analysis/AliasAnalysis.h"
29
#include "llvm/Analysis/ObjCARCAnalysisUtils.h"
30
#include "llvm/IR/Instructions.h"
31
#include "llvm/IR/Module.h"
32
#include "llvm/IR/Use.h"
33
#include "llvm/IR/User.h"
34
#include "llvm/IR/Value.h"
35
#include "llvm/Support/Casting.h"
36
#include <utility>
37
38
using namespace llvm;
39
using namespace llvm::objcarc;
40
41
bool ProvenanceAnalysis::relatedSelect(const SelectInst *A,
42
5
                                       const Value *B) {
43
5
  const DataLayout &DL = A->getModule()->getDataLayout();
44
5
  // If the values are Selects with the same condition, we can do a more precise
45
5
  // check: just check for relations between the values on corresponding arms.
46
5
  if (const SelectInst *SB = dyn_cast<SelectInst>(B))
47
0
    if (A->getCondition() == SB->getCondition())
48
0
      return related(A->getTrueValue(), SB->getTrueValue(), DL) ||
49
0
             related(A->getFalseValue(), SB->getFalseValue(), DL);
50
5
51
5
  // Check both arms of the Select node individually.
52
5
  return related(A->getTrueValue(), B, DL) ||
53
5
         
related(A->getFalseValue(), B, DL)0
;
54
5
}
55
56
bool ProvenanceAnalysis::relatedPHI(const PHINode *A,
57
140
                                    const Value *B) {
58
140
  const DataLayout &DL = A->getModule()->getDataLayout();
59
140
  // If the values are PHIs in the same block, we can do a more precise as well
60
140
  // as efficient check: just check for relations between the values on
61
140
  // corresponding edges.
62
140
  if (const PHINode *PNB = dyn_cast<PHINode>(B))
63
10
    if (PNB->getParent() == A->getParent()) {
64
13
      for (unsigned i = 0, e = A->getNumIncomingValues(); i != e; 
++i9
)
65
11
        if (related(A->getIncomingValue(i),
66
11
                    PNB->getIncomingValueForBlock(A->getIncomingBlock(i)), DL))
67
2
          return true;
68
4
      
return false2
;
69
136
    }
70
136
71
136
  // Check each unique source of the PHI node against B.
72
136
  SmallPtrSet<const Value *, 4> UniqueSrc;
73
434
  for (Value *PV1 : A->incoming_values()) {
74
434
    if (UniqueSrc.insert(PV1).second && 
related(PV1, B, DL)295
)
75
27
      return true;
76
434
  }
77
136
78
136
  // All of the arms checked out.
79
136
  
return false109
;
80
136
}
81
82
/// Test if the value of P, or any value covered by its provenance, is ever
83
/// stored within the function (not counting callees).
84
376
static bool IsStoredObjCPointer(const Value *P) {
85
376
  SmallPtrSet<const Value *, 8> Visited;
86
376
  SmallVector<const Value *, 8> Worklist;
87
376
  Worklist.push_back(P);
88
376
  Visited.insert(P);
89
1.32k
  do {
90
1.32k
    P = Worklist.pop_back_val();
91
2.15k
    for (const Use &U : P->uses()) {
92
2.15k
      const User *Ur = U.getUser();
93
2.15k
      if (isa<StoreInst>(Ur)) {
94
239
        if (U.getOperandNo() == 0)
95
44
          // The pointer is stored.
96
44
          return true;
97
195
        // The pointed is stored through.
98
195
        continue;
99
195
      }
100
1.91k
      if (isa<CallInst>(Ur))
101
820
        // The pointer is passed as an argument, ignore this.
102
820
        continue;
103
1.09k
      if (isa<PtrToIntInst>(P))
104
0
        // Assume the worst.
105
0
        return true;
106
1.09k
      if (Visited.insert(Ur).second)
107
948
        Worklist.push_back(Ur);
108
1.09k
    }
109
1.32k
  } while (
!Worklist.empty()1.28k
);
110
376
111
376
  // Everything checked out.
112
376
  
return false332
;
113
376
}
114
115
bool ProvenanceAnalysis::relatedCheck(const Value *A, const Value *B,
116
780
                                      const DataLayout &DL) {
117
780
  // Ask regular AliasAnalysis, for a first approximation.
118
780
  switch (AA->alias(A, B)) {
119
780
  case NoAlias:
120
73
    return false;
121
780
  case MustAlias:
122
0
  case PartialAlias:
123
0
    return true;
124
707
  case MayAlias:
125
707
    break;
126
707
  }
127
707
128
707
  bool AIsIdentified = IsObjCIdentifiedObject(A);
129
707
  bool BIsIdentified = IsObjCIdentifiedObject(B);
130
707
131
707
  // An ObjC-Identified object can't alias a load if it is never locally stored.
132
707
  if (AIsIdentified) {
133
589
    // Check for an obvious escape.
134
589
    if (isa<LoadInst>(B))
135
345
      return IsStoredObjCPointer(A);
136
244
    if (BIsIdentified) {
137
173
      // Check for an obvious escape.
138
173
      if (isa<LoadInst>(A))
139
6
        return IsStoredObjCPointer(B);
140
167
      // Both pointers are identified and escapes aren't an evident problem.
141
167
      return false;
142
167
    }
143
118
  } else if (BIsIdentified) {
144
51
    // Check for an obvious escape.
145
51
    if (isa<LoadInst>(A))
146
25
      return IsStoredObjCPointer(B);
147
164
  }
148
164
149
164
   // Special handling for PHI and Select.
150
164
  if (const PHINode *PN = dyn_cast<PHINode>(A))
151
56
    return relatedPHI(PN, B);
152
108
  if (const PHINode *PN = dyn_cast<PHINode>(B))
153
84
    return relatedPHI(PN, A);
154
24
  if (const SelectInst *S = dyn_cast<SelectInst>(A))
155
0
    return relatedSelect(S, B);
156
24
  if (const SelectInst *S = dyn_cast<SelectInst>(B))
157
5
    return relatedSelect(S, A);
158
19
159
19
  // Conservative.
160
19
  return true;
161
19
}
162
163
bool ProvenanceAnalysis::related(const Value *A, const Value *B,
164
1.60k
                                 const DataLayout &DL) {
165
1.60k
  A = GetUnderlyingObjCPtrCached(A, DL, UnderlyingObjCPtrCache);
166
1.60k
  B = GetUnderlyingObjCPtrCached(B, DL, UnderlyingObjCPtrCache);
167
1.60k
168
1.60k
  // Quick check.
169
1.60k
  if (A == B)
170
337
    return true;
171
1.27k
172
1.27k
  // Begin by inserting a conservative value into the map. If the insertion
173
1.27k
  // fails, we have the answer already. If it succeeds, leave it there until we
174
1.27k
  // compute the real answer to guard against recursive queries.
175
1.27k
  if (A > B) 
std::swap(A, B)397
;
176
1.27k
  std::pair<CachedResultsTy::iterator, bool> Pair =
177
1.27k
    CachedResults.insert(std::make_pair(ValuePairTy(A, B), true));
178
1.27k
  if (!Pair.second)
179
492
    return Pair.first->second;
180
780
181
780
  bool Result = relatedCheck(A, B, DL);
182
780
  CachedResults[ValuePairTy(A, B)] = Result;
183
780
  return Result;
184
780
}