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                                        const Value *B) {
43   // If the values are Selects with the same condition, we can do a more precise
44   // check: just check for relations between the values on corresponding arms.
45   if (const SelectInst *SB = dyn_cast<SelectInst>(B))
46     if (A->getCondition() == SB->getCondition())
47       return related(A->getTrueValue(), SB->getTrueValue()) ||
48              related(A->getFalseValue(), SB->getFalseValue());
49 
50   // Check both arms of the Select node individually.
51   return related(A->getTrueValue(), B) || related(A->getFalseValue(), B);
52 }
53 
54 bool ProvenanceAnalysis::relatedPHI(const PHINode *A,
55                                     const Value *B) {
56   // If the values are PHIs in the same block, we can do a more precise as well
57   // as efficient check: just check for relations between the values on
58   // corresponding edges.
59   if (const PHINode *PNB = dyn_cast<PHINode>(B))
60     if (PNB->getParent() == A->getParent()) {
61       for (unsigned i = 0, e = A->getNumIncomingValues(); i != e; ++i)
62         if (related(A->getIncomingValue(i),
63                     PNB->getIncomingValueForBlock(A->getIncomingBlock(i))))
64           return true;
65       return false;
66     }
67 
68   // Check each unique source of the PHI node against B.
69   SmallPtrSet<const Value *, 4> UniqueSrc;
70   for (Value *PV1 : A->incoming_values()) {
71     if (UniqueSrc.insert(PV1).second && related(PV1, B))
72       return true;
73   }
74 
75   // All of the arms checked out.
76   return false;
77 }
78 
79 /// Test if the value of P, or any value covered by its provenance, is ever
80 /// stored within the function (not counting callees).
81 static bool IsStoredObjCPointer(const Value *P) {
82   SmallPtrSet<const Value *, 8> Visited;
83   SmallVector<const Value *, 8> Worklist;
84   Worklist.push_back(P);
85   Visited.insert(P);
86   do {
87     P = Worklist.pop_back_val();
88     for (const Use &U : P->uses()) {
89       const User *Ur = U.getUser();
90       if (isa<StoreInst>(Ur)) {
91         if (U.getOperandNo() == 0)
92           // The pointer is stored.
93           return true;
94         // The pointed is stored through.
95         continue;
96       }
97       if (isa<CallInst>(Ur))
98         // The pointer is passed as an argument, ignore this.
99         continue;
100       if (isa<PtrToIntInst>(P))
101         // Assume the worst.
102         return true;
103       if (Visited.insert(Ur).second)
104         Worklist.push_back(Ur);
105     }
106   } while (!Worklist.empty());
107 
108   // Everything checked out.
109   return false;
110 }
111 
112 bool ProvenanceAnalysis::relatedCheck(const Value *A, const Value *B) {
113   // Ask regular AliasAnalysis, for a first approximation.
114   switch (AA->alias(A, B)) {
115   case AliasResult::NoAlias:
116     return false;
117   case AliasResult::MustAlias:
118   case AliasResult::PartialAlias:
119     return true;
120   case AliasResult::MayAlias:
121     break;
122   }
123 
124   bool AIsIdentified = IsObjCIdentifiedObject(A);
125   bool BIsIdentified = IsObjCIdentifiedObject(B);
126 
127   // An ObjC-Identified object can't alias a load if it is never locally stored.
128   if (AIsIdentified) {
129     // Check for an obvious escape.
130     if (isa<LoadInst>(B))
131       return IsStoredObjCPointer(A);
132     if (BIsIdentified) {
133       // Check for an obvious escape.
134       if (isa<LoadInst>(A))
135         return IsStoredObjCPointer(B);
136       // Both pointers are identified and escapes aren't an evident problem.
137       return false;
138     }
139   } else if (BIsIdentified) {
140     // Check for an obvious escape.
141     if (isa<LoadInst>(A))
142       return IsStoredObjCPointer(B);
143   }
144 
145    // Special handling for PHI and Select.
146   if (const PHINode *PN = dyn_cast<PHINode>(A))
147     return relatedPHI(PN, B);
148   if (const PHINode *PN = dyn_cast<PHINode>(B))
149     return relatedPHI(PN, A);
150   if (const SelectInst *S = dyn_cast<SelectInst>(A))
151     return relatedSelect(S, B);
152   if (const SelectInst *S = dyn_cast<SelectInst>(B))
153     return relatedSelect(S, A);
154 
155   // Conservative.
156   return true;
157 }
158 
159 bool ProvenanceAnalysis::related(const Value *A, const Value *B) {
160   A = GetUnderlyingObjCPtrCached(A, UnderlyingObjCPtrCache);
161   B = GetUnderlyingObjCPtrCached(B, UnderlyingObjCPtrCache);
162 
163   // Quick check.
164   if (A == B)
165     return true;
166 
167   // Begin by inserting a conservative value into the map. If the insertion
168   // fails, we have the answer already. If it succeeds, leave it there until we
169   // compute the real answer to guard against recursive queries.
170   std::pair<CachedResultsTy::iterator, bool> Pair =
171     CachedResults.insert(std::make_pair(ValuePairTy(A, B), true));
172   if (!Pair.second)
173     return Pair.first->second;
174 
175   bool Result = relatedCheck(A, B);
176   CachedResults[ValuePairTy(A, B)] = Result;
177   return Result;
178 }
179