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