]>
git.proxmox.com Git - rustc.git/blob - src/llvm/lib/Transforms/ObjCARC/ProvenanceAnalysis.cpp
1 //===- ProvenanceAnalysis.cpp - ObjC ARC Optimization ---------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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
16 /// WARNING: This file knows about certain library functions. It recognizes them
17 /// by name, and hardwires knowledge of their semantics.
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.
23 //===----------------------------------------------------------------------===//
26 #include "ProvenanceAnalysis.h"
27 #include "llvm/ADT/STLExtras.h"
28 #include "llvm/ADT/SmallPtrSet.h"
31 using namespace llvm::objcarc
;
33 bool ProvenanceAnalysis::relatedSelect(const SelectInst
*A
,
35 // If the values are Selects with the same condition, we can do a more precise
36 // check: just check for relations between the values on corresponding arms.
37 if (const SelectInst
*SB
= dyn_cast
<SelectInst
>(B
))
38 if (A
->getCondition() == SB
->getCondition())
39 return related(A
->getTrueValue(), SB
->getTrueValue()) ||
40 related(A
->getFalseValue(), SB
->getFalseValue());
42 // Check both arms of the Select node individually.
43 return related(A
->getTrueValue(), B
) ||
44 related(A
->getFalseValue(), B
);
47 bool ProvenanceAnalysis::relatedPHI(const PHINode
*A
,
49 // If the values are PHIs in the same block, we can do a more precise as well
50 // as efficient check: just check for relations between the values on
51 // corresponding edges.
52 if (const PHINode
*PNB
= dyn_cast
<PHINode
>(B
))
53 if (PNB
->getParent() == A
->getParent()) {
54 for (unsigned i
= 0, e
= A
->getNumIncomingValues(); i
!= e
; ++i
)
55 if (related(A
->getIncomingValue(i
),
56 PNB
->getIncomingValueForBlock(A
->getIncomingBlock(i
))))
61 // Check each unique source of the PHI node against B.
62 SmallPtrSet
<const Value
*, 4> UniqueSrc
;
63 for (unsigned i
= 0, e
= A
->getNumIncomingValues(); i
!= e
; ++i
) {
64 const Value
*PV1
= A
->getIncomingValue(i
);
65 if (UniqueSrc
.insert(PV1
).second
&& related(PV1
, B
))
69 // All of the arms checked out.
73 /// Test if the value of P, or any value covered by its provenance, is ever
74 /// stored within the function (not counting callees).
75 static bool IsStoredObjCPointer(const Value
*P
) {
76 SmallPtrSet
<const Value
*, 8> Visited
;
77 SmallVector
<const Value
*, 8> Worklist
;
78 Worklist
.push_back(P
);
81 P
= Worklist
.pop_back_val();
82 for (const Use
&U
: P
->uses()) {
83 const User
*Ur
= U
.getUser();
84 if (isa
<StoreInst
>(Ur
)) {
85 if (U
.getOperandNo() == 0)
86 // The pointer is stored.
88 // The pointed is stored through.
91 if (isa
<CallInst
>(Ur
))
92 // The pointer is passed as an argument, ignore this.
94 if (isa
<PtrToIntInst
>(P
))
97 if (Visited
.insert(Ur
).second
)
98 Worklist
.push_back(Ur
);
100 } while (!Worklist
.empty());
102 // Everything checked out.
106 bool ProvenanceAnalysis::relatedCheck(const Value
*A
,
108 // Skip past provenance pass-throughs.
109 A
= GetUnderlyingObjCPtr(A
);
110 B
= GetUnderlyingObjCPtr(B
);
116 // Ask regular AliasAnalysis, for a first approximation.
117 switch (AA
->alias(A
, B
)) {
118 case AliasAnalysis::NoAlias
:
120 case AliasAnalysis::MustAlias
:
121 case AliasAnalysis::PartialAlias
:
123 case AliasAnalysis::MayAlias
:
127 bool AIsIdentified
= IsObjCIdentifiedObject(A
);
128 bool BIsIdentified
= IsObjCIdentifiedObject(B
);
130 // An ObjC-Identified object can't alias a load if it is never locally stored.
132 // Check for an obvious escape.
133 if (isa
<LoadInst
>(B
))
134 return IsStoredObjCPointer(A
);
136 // Check for an obvious escape.
137 if (isa
<LoadInst
>(A
))
138 return IsStoredObjCPointer(B
);
139 // Both pointers are identified and escapes aren't an evident problem.
142 } else if (BIsIdentified
) {
143 // Check for an obvious escape.
144 if (isa
<LoadInst
>(A
))
145 return IsStoredObjCPointer(B
);
148 // Special handling for PHI and Select.
149 if (const PHINode
*PN
= dyn_cast
<PHINode
>(A
))
150 return relatedPHI(PN
, B
);
151 if (const PHINode
*PN
= dyn_cast
<PHINode
>(B
))
152 return relatedPHI(PN
, A
);
153 if (const SelectInst
*S
= dyn_cast
<SelectInst
>(A
))
154 return relatedSelect(S
, B
);
155 if (const SelectInst
*S
= dyn_cast
<SelectInst
>(B
))
156 return relatedSelect(S
, A
);
162 bool ProvenanceAnalysis::related(const Value
*A
,
164 // Begin by inserting a conservative value into the map. If the insertion
165 // fails, we have the answer already. If it succeeds, leave it there until we
166 // compute the real answer to guard against recursive queries.
167 if (A
> B
) std::swap(A
, B
);
168 std::pair
<CachedResultsTy::iterator
, bool> Pair
=
169 CachedResults
.insert(std::make_pair(ValuePairTy(A
, B
), true));
171 return Pair
.first
->second
;
173 bool Result
= relatedCheck(A
, B
);
174 CachedResults
[ValuePairTy(A
, B
)] = Result
;