LLVM  10.0.0svn
ProvenanceAnalysis.cpp
Go to the documentation of this file.
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"
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  const Value *B) {
43  const DataLayout &DL = A->getModule()->getDataLayout();
44  // If the values are Selects with the same condition, we can do a more precise
45  // check: just check for relations between the values on corresponding arms.
46  if (const SelectInst *SB = dyn_cast<SelectInst>(B))
47  if (A->getCondition() == SB->getCondition())
48  return related(A->getTrueValue(), SB->getTrueValue(), DL) ||
49  related(A->getFalseValue(), SB->getFalseValue(), DL);
50 
51  // Check both arms of the Select node individually.
52  return related(A->getTrueValue(), B, DL) ||
53  related(A->getFalseValue(), B, DL);
54 }
55 
56 bool ProvenanceAnalysis::relatedPHI(const PHINode *A,
57  const Value *B) {
58  const DataLayout &DL = A->getModule()->getDataLayout();
59  // If the values are PHIs in the same block, we can do a more precise as well
60  // as efficient check: just check for relations between the values on
61  // corresponding edges.
62  if (const PHINode *PNB = dyn_cast<PHINode>(B))
63  if (PNB->getParent() == A->getParent()) {
64  for (unsigned i = 0, e = A->getNumIncomingValues(); i != e; ++i)
65  if (related(A->getIncomingValue(i),
66  PNB->getIncomingValueForBlock(A->getIncomingBlock(i)), DL))
67  return true;
68  return false;
69  }
70 
71  // Check each unique source of the PHI node against B.
73  for (Value *PV1 : A->incoming_values()) {
74  if (UniqueSrc.insert(PV1).second && related(PV1, B, DL))
75  return true;
76  }
77 
78  // All of the arms checked out.
79  return false;
80 }
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 static bool IsStoredObjCPointer(const Value *P) {
87  Worklist.push_back(P);
88  Visited.insert(P);
89  do {
90  P = Worklist.pop_back_val();
91  for (const Use &U : P->uses()) {
92  const User *Ur = U.getUser();
93  if (isa<StoreInst>(Ur)) {
94  if (U.getOperandNo() == 0)
95  // The pointer is stored.
96  return true;
97  // The pointed is stored through.
98  continue;
99  }
100  if (isa<CallInst>(Ur))
101  // The pointer is passed as an argument, ignore this.
102  continue;
103  if (isa<PtrToIntInst>(P))
104  // Assume the worst.
105  return true;
106  if (Visited.insert(Ur).second)
107  Worklist.push_back(Ur);
108  }
109  } while (!Worklist.empty());
110 
111  // Everything checked out.
112  return false;
113 }
114 
115 bool ProvenanceAnalysis::relatedCheck(const Value *A, const Value *B,
116  const DataLayout &DL) {
117  // Ask regular AliasAnalysis, for a first approximation.
118  switch (AA->alias(A, B)) {
119  case NoAlias:
120  return false;
121  case MustAlias:
122  case PartialAlias:
123  return true;
124  case MayAlias:
125  break;
126  }
127 
128  bool AIsIdentified = IsObjCIdentifiedObject(A);
129  bool BIsIdentified = IsObjCIdentifiedObject(B);
130 
131  // An ObjC-Identified object can't alias a load if it is never locally stored.
132  if (AIsIdentified) {
133  // Check for an obvious escape.
134  if (isa<LoadInst>(B))
135  return IsStoredObjCPointer(A);
136  if (BIsIdentified) {
137  // Check for an obvious escape.
138  if (isa<LoadInst>(A))
139  return IsStoredObjCPointer(B);
140  // Both pointers are identified and escapes aren't an evident problem.
141  return false;
142  }
143  } else if (BIsIdentified) {
144  // Check for an obvious escape.
145  if (isa<LoadInst>(A))
146  return IsStoredObjCPointer(B);
147  }
148 
149  // Special handling for PHI and Select.
150  if (const PHINode *PN = dyn_cast<PHINode>(A))
151  return relatedPHI(PN, B);
152  if (const PHINode *PN = dyn_cast<PHINode>(B))
153  return relatedPHI(PN, A);
154  if (const SelectInst *S = dyn_cast<SelectInst>(A))
155  return relatedSelect(S, B);
156  if (const SelectInst *S = dyn_cast<SelectInst>(B))
157  return relatedSelect(S, A);
158 
159  // Conservative.
160  return true;
161 }
162 
163 bool ProvenanceAnalysis::related(const Value *A, const Value *B,
164  const DataLayout &DL) {
165  A = GetUnderlyingObjCPtrCached(A, DL, UnderlyingObjCPtrCache);
166  B = GetUnderlyingObjCPtrCached(B, DL, UnderlyingObjCPtrCache);
167 
168  // Quick check.
169  if (A == B)
170  return true;
171 
172  // Begin by inserting a conservative value into the map. If the insertion
173  // fails, we have the answer already. If it succeeds, leave it there until we
174  // compute the real answer to guard against recursive queries.
175  if (A > B) std::swap(A, B);
176  std::pair<CachedResultsTy::iterator, bool> Pair =
177  CachedResults.insert(std::make_pair(ValuePairTy(A, B), true));
178  if (!Pair.second)
179  return Pair.first->second;
180 
181  bool Result = relatedCheck(A, B, DL);
182  CachedResults[ValuePairTy(A, B)] = Result;
183  return Result;
184 }
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
iterator_range< use_iterator > uses()
Definition: Value.h:374
This class represents lattice values for constants.
Definition: AllocatorList.h:23
const Value * getTrueValue() const
The two locations do not alias at all.
Definition: AliasAnalysis.h:84
This defines the Use class.
bool IsObjCIdentifiedObject(const Value *V)
Return true if this value refers to a distinct and identifiable object.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:195
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
The main low level interface to the alias analysis implementation.
This class represents the LLVM &#39;select&#39; instruction.
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:369
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
#define P(N)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static bool IsStoredObjCPointer(const Value *P)
Test if the value of P, or any value covered by its provenance, is ever stored within the function (n...
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:370
const Value * getCondition() const
This file defines common analysis utilities used by the ObjC ARC Optimizer.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
The two locations may or may not alias. This is the least precise result.
Definition: AliasAnalysis.h:86
The two locations precisely alias each other.
Definition: AliasAnalysis.h:90
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
This file declares a special form of Alias Analysis called ``Provenance Analysis&#39;&#39;.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
Module.h This file contains the declarations for the Module class.
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
const Value * GetUnderlyingObjCPtrCached(const Value *V, const DataLayout &DL, DenseMap< const Value *, WeakTrackingVH > &Cache)
A wrapper for GetUnderlyingObjCPtr used for results memoization.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
bool related(const Value *A, const Value *B, const DataLayout &DL)
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:55
const Value * getFalseValue() const
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
LLVM Value Representation.
Definition: Value.h:73
The two locations alias, but only due to a partial overlap.
Definition: AliasAnalysis.h:88
op_range incoming_values()
const BasicBlock * getParent() const
Definition: Instruction.h:66