blob: 2f5fbec66d2971845af9e8ce7eebb4ebb9ce45ec [file] [log] [blame]
Hans Wennborgc5ec73d2014-11-21 18:58:23 +00001//===- LazyValueInfo.cpp - Value constraint analysis ------------*- C++ -*-===//
Chris Lattner741c94c2009-11-11 00:22:30 +00002//
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// This file defines the interface for lazy computation of value constraint
11// information.
12//
13//===----------------------------------------------------------------------===//
14
15#include "llvm/Analysis/LazyValueInfo.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000016#include "llvm/ADT/DenseSet.h"
17#include "llvm/ADT/STLExtras.h"
Chandler Carruth66b31302015-01-04 12:03:27 +000018#include "llvm/Analysis/AssumptionCache.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000019#include "llvm/Analysis/ConstantFolding.h"
Chandler Carruth62d42152015-01-15 02:16:27 +000020#include "llvm/Analysis/TargetLibraryInfo.h"
Dan Gohmana4fcd242010-12-15 20:02:24 +000021#include "llvm/Analysis/ValueTracking.h"
Chandler Carruth1305dc32014-03-04 11:45:46 +000022#include "llvm/IR/CFG.h"
Chandler Carruth8cd041e2014-03-04 12:24:34 +000023#include "llvm/IR/ConstantRange.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000024#include "llvm/IR/Constants.h"
25#include "llvm/IR/DataLayout.h"
Hal Finkel7e184492014-09-07 20:29:59 +000026#include "llvm/IR/Dominators.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000027#include "llvm/IR/Instructions.h"
28#include "llvm/IR/IntrinsicInst.h"
Philip Reameseb3e9da2015-10-29 03:57:17 +000029#include "llvm/IR/LLVMContext.h"
Chandler Carruth820a9082014-03-04 11:08:18 +000030#include "llvm/IR/PatternMatch.h"
Chandler Carruth4220e9c2014-03-04 11:17:44 +000031#include "llvm/IR/ValueHandle.h"
Chris Lattnerb584d1e2009-11-12 01:22:16 +000032#include "llvm/Support/Debug.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000033#include "llvm/Support/raw_ostream.h"
Bill Wendling4ec081a2012-01-11 23:43:34 +000034#include <map>
Nick Lewycky55a700b2010-12-18 01:00:40 +000035#include <stack>
Chris Lattner741c94c2009-11-11 00:22:30 +000036using namespace llvm;
Benjamin Kramerd9d80b12012-03-02 15:34:43 +000037using namespace PatternMatch;
Chris Lattner741c94c2009-11-11 00:22:30 +000038
Chandler Carruthf1221bd2014-04-22 02:48:03 +000039#define DEBUG_TYPE "lazy-value-info"
40
Sean Silva687019f2016-06-13 22:01:25 +000041char LazyValueInfoWrapperPass::ID = 0;
42INITIALIZE_PASS_BEGIN(LazyValueInfoWrapperPass, "lazy-value-info",
Chad Rosier43a33062011-12-02 01:26:24 +000043 "Lazy Value Information Analysis", false, true)
Chandler Carruth66b31302015-01-04 12:03:27 +000044INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
Chandler Carruthb98f63d2015-01-15 10:41:28 +000045INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
Sean Silva687019f2016-06-13 22:01:25 +000046INITIALIZE_PASS_END(LazyValueInfoWrapperPass, "lazy-value-info",
Owen Andersondf7a4f22010-10-07 22:25:06 +000047 "Lazy Value Information Analysis", false, true)
Chris Lattner741c94c2009-11-11 00:22:30 +000048
49namespace llvm {
Sean Silva687019f2016-06-13 22:01:25 +000050 FunctionPass *createLazyValueInfoPass() { return new LazyValueInfoWrapperPass(); }
Chris Lattner741c94c2009-11-11 00:22:30 +000051}
52
Sean Silva687019f2016-06-13 22:01:25 +000053char LazyValueAnalysis::PassID;
Chris Lattnerfde1f8d2009-11-11 02:08:33 +000054
55//===----------------------------------------------------------------------===//
56// LVILatticeVal
57//===----------------------------------------------------------------------===//
58
Sanjay Patel2a385e22015-01-09 16:47:20 +000059/// This is the information tracked by LazyValueInfo for each value.
Chris Lattnerfde1f8d2009-11-11 02:08:33 +000060///
61/// FIXME: This is basically just for bringup, this can be made a lot more rich
62/// in the future.
63///
64namespace {
65class LVILatticeVal {
66 enum LatticeValueTy {
Philip Reames3bb28322016-04-25 18:48:43 +000067 /// This Value has no known value yet. As a result, this implies the
68 /// producing instruction is dead. Caution: We use this as the starting
69 /// state in our local meet rules. In this usage, it's taken to mean
NAKAMURA Takumif2529512016-07-04 01:26:27 +000070 /// "nothing known yet".
Chris Lattnerfde1f8d2009-11-11 02:08:33 +000071 undefined,
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +000072
Philip Reames3bb28322016-04-25 18:48:43 +000073 /// This Value has a specific constant value. (For integers, constantrange
74 /// is used instead.)
Chris Lattnerfde1f8d2009-11-11 02:08:33 +000075 constant,
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +000076
Philip Reames3bb28322016-04-25 18:48:43 +000077 /// This Value is known to not have the specified value. (For integers,
78 /// constantrange is used instead.)
Chris Lattner565ee2f2009-11-12 04:36:58 +000079 notconstant,
Chad Rosier43a33062011-12-02 01:26:24 +000080
Philip Reames3bb28322016-04-25 18:48:43 +000081 /// The Value falls within this range. (Used only for integer typed values.)
Owen Anderson0f306a42010-08-05 22:59:19 +000082 constantrange,
Chad Rosier43a33062011-12-02 01:26:24 +000083
Philip Reames3bb28322016-04-25 18:48:43 +000084 /// We can not precisely model the dynamic values this value might take.
Chris Lattnerfde1f8d2009-11-11 02:08:33 +000085 overdefined
86 };
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +000087
Chris Lattnerfde1f8d2009-11-11 02:08:33 +000088 /// Val: This stores the current lattice value along with the Constant* for
Chris Lattner565ee2f2009-11-12 04:36:58 +000089 /// the constant if this is a 'constant' or 'notconstant' value.
Owen Andersonc3a14132010-08-05 22:10:46 +000090 LatticeValueTy Tag;
91 Constant *Val;
Owen Anderson0f306a42010-08-05 22:59:19 +000092 ConstantRange Range;
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +000093
Chris Lattnerfde1f8d2009-11-11 02:08:33 +000094public:
Craig Topper9f008862014-04-15 04:59:12 +000095 LVILatticeVal() : Tag(undefined), Val(nullptr), Range(1, true) {}
Chris Lattnerfde1f8d2009-11-11 02:08:33 +000096
Chris Lattner19019ea2009-11-11 22:48:44 +000097 static LVILatticeVal get(Constant *C) {
98 LVILatticeVal Res;
Nick Lewycky11678bd2010-12-15 18:57:18 +000099 if (!isa<UndefValue>(C))
Owen Anderson185fe002010-08-10 20:03:09 +0000100 Res.markConstant(C);
Chris Lattner19019ea2009-11-11 22:48:44 +0000101 return Res;
102 }
Chris Lattner565ee2f2009-11-12 04:36:58 +0000103 static LVILatticeVal getNot(Constant *C) {
104 LVILatticeVal Res;
Nick Lewycky11678bd2010-12-15 18:57:18 +0000105 if (!isa<UndefValue>(C))
Owen Anderson185fe002010-08-10 20:03:09 +0000106 Res.markNotConstant(C);
Chris Lattner565ee2f2009-11-12 04:36:58 +0000107 return Res;
108 }
Owen Anderson5f1dd092010-08-10 23:20:01 +0000109 static LVILatticeVal getRange(ConstantRange CR) {
110 LVILatticeVal Res;
Benjamin Kramer2337c1f2016-02-20 10:40:34 +0000111 Res.markConstantRange(std::move(CR));
Owen Anderson5f1dd092010-08-10 23:20:01 +0000112 return Res;
113 }
Akira Hatanaka2992bee2015-12-11 00:49:47 +0000114 static LVILatticeVal getOverdefined() {
115 LVILatticeVal Res;
116 Res.markOverdefined();
117 return Res;
118 }
NAKAMURA Takumi4cb46e62016-07-04 01:26:33 +0000119
Owen Anderson0f306a42010-08-05 22:59:19 +0000120 bool isUndefined() const { return Tag == undefined; }
121 bool isConstant() const { return Tag == constant; }
122 bool isNotConstant() const { return Tag == notconstant; }
123 bool isConstantRange() const { return Tag == constantrange; }
124 bool isOverdefined() const { return Tag == overdefined; }
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000125
Chris Lattnerfde1f8d2009-11-11 02:08:33 +0000126 Constant *getConstant() const {
127 assert(isConstant() && "Cannot get the constant of a non-constant!");
Owen Andersonc3a14132010-08-05 22:10:46 +0000128 return Val;
Chris Lattnerfde1f8d2009-11-11 02:08:33 +0000129 }
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000130
Chris Lattner565ee2f2009-11-12 04:36:58 +0000131 Constant *getNotConstant() const {
132 assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
Owen Andersonc3a14132010-08-05 22:10:46 +0000133 return Val;
Chris Lattnerfde1f8d2009-11-11 02:08:33 +0000134 }
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000135
Owen Anderson0f306a42010-08-05 22:59:19 +0000136 ConstantRange getConstantRange() const {
137 assert(isConstantRange() &&
138 "Cannot get the constant-range of a non-constant-range!");
139 return Range;
140 }
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000141
Sanjay Patel2a385e22015-01-09 16:47:20 +0000142 /// Return true if this is a change in status.
Chris Lattnerfde1f8d2009-11-11 02:08:33 +0000143 bool markOverdefined() {
144 if (isOverdefined())
145 return false;
Owen Andersonc3a14132010-08-05 22:10:46 +0000146 Tag = overdefined;
Chris Lattnerfde1f8d2009-11-11 02:08:33 +0000147 return true;
148 }
149
Sanjay Patel2a385e22015-01-09 16:47:20 +0000150 /// Return true if this is a change in status.
Chris Lattnerfde1f8d2009-11-11 02:08:33 +0000151 bool markConstant(Constant *V) {
Nick Lewycky11678bd2010-12-15 18:57:18 +0000152 assert(V && "Marking constant with NULL");
153 if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
154 return markConstantRange(ConstantRange(CI->getValue()));
155 if (isa<UndefValue>(V))
Chris Lattnerfde1f8d2009-11-11 02:08:33 +0000156 return false;
Nick Lewycky11678bd2010-12-15 18:57:18 +0000157
158 assert((!isConstant() || getConstant() == V) &&
159 "Marking constant with different value");
Chris Lattnerfde1f8d2009-11-11 02:08:33 +0000160 assert(isUndefined());
Owen Andersonc3a14132010-08-05 22:10:46 +0000161 Tag = constant;
Owen Andersonc3a14132010-08-05 22:10:46 +0000162 Val = V;
Chris Lattner19019ea2009-11-11 22:48:44 +0000163 return true;
164 }
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000165
Sanjay Patel2a385e22015-01-09 16:47:20 +0000166 /// Return true if this is a change in status.
Chris Lattner565ee2f2009-11-12 04:36:58 +0000167 bool markNotConstant(Constant *V) {
Chris Lattner565ee2f2009-11-12 04:36:58 +0000168 assert(V && "Marking constant with NULL");
Nick Lewycky11678bd2010-12-15 18:57:18 +0000169 if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
170 return markConstantRange(ConstantRange(CI->getValue()+1, CI->getValue()));
171 if (isa<UndefValue>(V))
172 return false;
173
174 assert((!isConstant() || getConstant() != V) &&
175 "Marking constant !constant with same value");
176 assert((!isNotConstant() || getNotConstant() == V) &&
177 "Marking !constant with different value");
178 assert(isUndefined() || isConstant());
179 Tag = notconstant;
Owen Andersonc3a14132010-08-05 22:10:46 +0000180 Val = V;
Chris Lattner565ee2f2009-11-12 04:36:58 +0000181 return true;
182 }
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000183
Sanjay Patel2a385e22015-01-09 16:47:20 +0000184 /// Return true if this is a change in status.
Benjamin Kramer2337c1f2016-02-20 10:40:34 +0000185 bool markConstantRange(ConstantRange NewR) {
Owen Anderson0f306a42010-08-05 22:59:19 +0000186 if (isConstantRange()) {
187 if (NewR.isEmptySet())
188 return markOverdefined();
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000189
Nuno Lopese6e04902012-06-28 01:16:18 +0000190 bool changed = Range != NewR;
Benjamin Kramer2337c1f2016-02-20 10:40:34 +0000191 Range = std::move(NewR);
Owen Anderson0f306a42010-08-05 22:59:19 +0000192 return changed;
193 }
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000194
Owen Anderson0f306a42010-08-05 22:59:19 +0000195 assert(isUndefined());
196 if (NewR.isEmptySet())
197 return markOverdefined();
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000198
Owen Anderson0f306a42010-08-05 22:59:19 +0000199 Tag = constantrange;
Benjamin Kramer2337c1f2016-02-20 10:40:34 +0000200 Range = std::move(NewR);
Owen Anderson0f306a42010-08-05 22:59:19 +0000201 return true;
202 }
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000203
Sanjay Patel2a385e22015-01-09 16:47:20 +0000204 /// Merge the specified lattice value into this one, updating this
Chris Lattner19019ea2009-11-11 22:48:44 +0000205 /// one and returning true if anything changed.
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000206 bool mergeIn(const LVILatticeVal &RHS, const DataLayout &DL) {
Chris Lattner19019ea2009-11-11 22:48:44 +0000207 if (RHS.isUndefined() || isOverdefined()) return false;
208 if (RHS.isOverdefined()) return markOverdefined();
209
Nick Lewycky11678bd2010-12-15 18:57:18 +0000210 if (isUndefined()) {
211 Tag = RHS.Tag;
212 Val = RHS.Val;
213 Range = RHS.Range;
214 return true;
Chris Lattner22db4b52009-11-12 04:57:13 +0000215 }
216
Nick Lewycky11678bd2010-12-15 18:57:18 +0000217 if (isConstant()) {
218 if (RHS.isConstant()) {
219 if (Val == RHS.Val)
220 return false;
221 return markOverdefined();
222 }
223
224 if (RHS.isNotConstant()) {
225 if (Val == RHS.Val)
226 return markOverdefined();
227
228 // Unless we can prove that the two Constants are different, we must
229 // move to overdefined.
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000230 if (ConstantInt *Res =
231 dyn_cast<ConstantInt>(ConstantFoldCompareInstOperands(
232 CmpInst::ICMP_NE, getConstant(), RHS.getNotConstant(), DL)))
Nick Lewycky11678bd2010-12-15 18:57:18 +0000233 if (Res->isOne())
234 return markNotConstant(RHS.getNotConstant());
235
236 return markOverdefined();
237 }
238
Chris Lattner19019ea2009-11-11 22:48:44 +0000239 return markOverdefined();
Nick Lewycky11678bd2010-12-15 18:57:18 +0000240 }
241
242 if (isNotConstant()) {
243 if (RHS.isConstant()) {
244 if (Val == RHS.Val)
245 return markOverdefined();
246
247 // Unless we can prove that the two Constants are different, we must
248 // move to overdefined.
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000249 if (ConstantInt *Res =
250 dyn_cast<ConstantInt>(ConstantFoldCompareInstOperands(
251 CmpInst::ICMP_NE, getNotConstant(), RHS.getConstant(), DL)))
Nick Lewycky11678bd2010-12-15 18:57:18 +0000252 if (Res->isOne())
253 return false;
254
255 return markOverdefined();
256 }
257
258 if (RHS.isNotConstant()) {
259 if (Val == RHS.Val)
260 return false;
261 return markOverdefined();
262 }
263
264 return markOverdefined();
265 }
266
267 assert(isConstantRange() && "New LVILattice type?");
268 if (!RHS.isConstantRange())
269 return markOverdefined();
270
271 ConstantRange NewR = Range.unionWith(RHS.getConstantRange());
272 if (NewR.isFullSet())
273 return markOverdefined();
274 return markConstantRange(NewR);
Chris Lattnerfde1f8d2009-11-11 02:08:33 +0000275 }
Chris Lattnerfde1f8d2009-11-11 02:08:33 +0000276};
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000277
Chris Lattnerfde1f8d2009-11-11 02:08:33 +0000278} // end anonymous namespace.
279
Chris Lattner19019ea2009-11-11 22:48:44 +0000280namespace llvm {
Chandler Carruth2b1ba482011-04-18 18:49:44 +0000281raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val)
282 LLVM_ATTRIBUTE_USED;
Chris Lattner19019ea2009-11-11 22:48:44 +0000283raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) {
284 if (Val.isUndefined())
285 return OS << "undefined";
286 if (Val.isOverdefined())
287 return OS << "overdefined";
Chris Lattner565ee2f2009-11-12 04:36:58 +0000288
289 if (Val.isNotConstant())
290 return OS << "notconstant<" << *Val.getNotConstant() << '>';
Davide Italianobd543d02016-05-25 22:29:34 +0000291 if (Val.isConstantRange())
Owen Anderson8afac042010-08-09 20:50:46 +0000292 return OS << "constantrange<" << Val.getConstantRange().getLower() << ", "
293 << Val.getConstantRange().getUpper() << '>';
Chris Lattner19019ea2009-11-11 22:48:44 +0000294 return OS << "constant<" << *Val.getConstant() << '>';
295}
Alexander Kornienkof00654e2015-06-23 09:49:53 +0000296}
Chris Lattnerfde1f8d2009-11-11 02:08:33 +0000297
Philip Reamesed8cd0d2016-02-02 22:03:19 +0000298/// Returns true if this lattice value represents at most one possible value.
299/// This is as precise as any lattice value can get while still representing
300/// reachable code.
Benjamin Kramerc321e532016-06-08 19:09:22 +0000301static bool hasSingleValue(const LVILatticeVal &Val) {
Philip Reamesed8cd0d2016-02-02 22:03:19 +0000302 if (Val.isConstantRange() &&
303 Val.getConstantRange().isSingleElement())
304 // Integer constants are single element ranges
305 return true;
306 if (Val.isConstant())
307 // Non integer constants
308 return true;
309 return false;
310}
311
312/// Combine two sets of facts about the same value into a single set of
313/// facts. Note that this method is not suitable for merging facts along
314/// different paths in a CFG; that's what the mergeIn function is for. This
315/// is for merging facts gathered about the same value at the same location
316/// through two independent means.
317/// Notes:
318/// * This method does not promise to return the most precise possible lattice
319/// value implied by A and B. It is allowed to return any lattice element
320/// which is at least as strong as *either* A or B (unless our facts
NAKAMURA Takumif2529512016-07-04 01:26:27 +0000321/// conflict, see below).
Philip Reamesed8cd0d2016-02-02 22:03:19 +0000322/// * Due to unreachable code, the intersection of two lattice values could be
323/// contradictory. If this happens, we return some valid lattice value so as
324/// not confuse the rest of LVI. Ideally, we'd always return Undefined, but
325/// we do not make this guarantee. TODO: This would be a useful enhancement.
326static LVILatticeVal intersect(LVILatticeVal A, LVILatticeVal B) {
327 // Undefined is the strongest state. It means the value is known to be along
328 // an unreachable path.
329 if (A.isUndefined())
330 return A;
331 if (B.isUndefined())
332 return B;
333
334 // If we gave up for one, but got a useable fact from the other, use it.
335 if (A.isOverdefined())
336 return B;
337 if (B.isOverdefined())
338 return A;
339
340 // Can't get any more precise than constants.
341 if (hasSingleValue(A))
342 return A;
343 if (hasSingleValue(B))
344 return B;
345
346 // Could be either constant range or not constant here.
347 if (!A.isConstantRange() || !B.isConstantRange()) {
348 // TODO: Arbitrary choice, could be improved
349 return A;
350 }
351
352 // Intersect two constant ranges
353 ConstantRange Range =
354 A.getConstantRange().intersectWith(B.getConstantRange());
355 // Note: An empty range is implicitly converted to overdefined internally.
356 // TODO: We could instead use Undefined here since we've proven a conflict
NAKAMURA Takumif2529512016-07-04 01:26:27 +0000357 // and thus know this path must be unreachable.
Benjamin Kramer2337c1f2016-02-20 10:40:34 +0000358 return LVILatticeVal::getRange(std::move(Range));
Philip Reamesed8cd0d2016-02-02 22:03:19 +0000359}
Philip Reamesd1f829d2016-02-02 21:57:37 +0000360
Chris Lattnerfde1f8d2009-11-11 02:08:33 +0000361//===----------------------------------------------------------------------===//
Chris Lattneraf025d32009-11-15 19:59:49 +0000362// LazyValueInfoCache Decl
Chris Lattnerfde1f8d2009-11-11 02:08:33 +0000363//===----------------------------------------------------------------------===//
364
Chris Lattneraf025d32009-11-15 19:59:49 +0000365namespace {
Sanjay Patel2a385e22015-01-09 16:47:20 +0000366 /// A callback value handle updates the cache when values are erased.
Owen Anderson118ac802011-01-05 21:15:29 +0000367 class LazyValueInfoCache;
David Blaikie774b5842015-08-03 22:30:24 +0000368 struct LVIValueHandle final : public CallbackVH {
Justin Lebar58b377e2016-07-27 22:33:36 +0000369 // Needs to access getValPtr(), which is protected.
370 friend struct DenseMapInfo<LVIValueHandle>;
371
Owen Anderson118ac802011-01-05 21:15:29 +0000372 LazyValueInfoCache *Parent;
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000373
Owen Anderson118ac802011-01-05 21:15:29 +0000374 LVIValueHandle(Value *V, LazyValueInfoCache *P)
375 : CallbackVH(V), Parent(P) { }
Craig Toppere9ba7592014-03-05 07:30:04 +0000376
377 void deleted() override;
378 void allUsesReplacedWith(Value *V) override {
Owen Anderson118ac802011-01-05 21:15:29 +0000379 deleted();
380 }
381 };
Justin Lebar58b377e2016-07-27 22:33:36 +0000382} // end anonymous namespace
Owen Anderson118ac802011-01-05 21:15:29 +0000383
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000384namespace {
Sanjay Patel2a385e22015-01-09 16:47:20 +0000385 /// This is the cache kept by LazyValueInfo which
Chris Lattneraf025d32009-11-15 19:59:49 +0000386 /// maintains information about queries across the clients' queries.
387 class LazyValueInfoCache {
Sanjay Patel2a385e22015-01-09 16:47:20 +0000388 /// This is all of the cached block information for exactly one Value*.
389 /// The entries are sorted by the BasicBlock* of the
Chris Lattneraf025d32009-11-15 19:59:49 +0000390 /// entries, allowing us to do a lookup with a binary search.
Akira Hatanaka2992bee2015-12-11 00:49:47 +0000391 /// Over-defined lattice values are recorded in OverDefinedCache to reduce
392 /// memory overhead.
Justin Lebar58b377e2016-07-27 22:33:36 +0000393 struct ValueCacheEntryTy {
394 ValueCacheEntryTy(Value *V, LazyValueInfoCache *P) : Handle(V, P) {}
395 LVIValueHandle Handle;
396 SmallDenseMap<AssertingVH<BasicBlock>, LVILatticeVal, 4> BlockVals;
397 };
Chris Lattneraf025d32009-11-15 19:59:49 +0000398
Sanjay Patel2a385e22015-01-09 16:47:20 +0000399 /// This is all of the cached information for all values,
Owen Anderson6f060af2011-01-05 23:26:22 +0000400 /// mapped from Value* to key information.
Justin Lebar58b377e2016-07-27 22:33:36 +0000401 DenseMap<Value *, std::unique_ptr<ValueCacheEntryTy>> ValueCache;
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000402
Sanjay Patel2a385e22015-01-09 16:47:20 +0000403 /// This tracks, on a per-block basis, the set of values that are
Akira Hatanaka2992bee2015-12-11 00:49:47 +0000404 /// over-defined at the end of that block.
Bruno Cardoso Lopes6ac4ea42015-08-18 16:34:27 +0000405 typedef DenseMap<AssertingVH<BasicBlock>, SmallPtrSet<Value *, 4>>
406 OverDefinedCacheTy;
407 OverDefinedCacheTy OverDefinedCache;
Benjamin Kramer36647082011-12-03 15:16:45 +0000408
Sanjay Patel2a385e22015-01-09 16:47:20 +0000409 /// Keep track of all blocks that we have ever seen, so we
Benjamin Kramer36647082011-12-03 15:16:45 +0000410 /// don't spend time removing unused blocks from our caches.
411 DenseSet<AssertingVH<BasicBlock> > SeenBlocks;
412
Sanjay Patel2a385e22015-01-09 16:47:20 +0000413 /// This stack holds the state of the value solver during a query.
414 /// It basically emulates the callstack of the naive
Owen Anderson6f060af2011-01-05 23:26:22 +0000415 /// recursive value lookup process.
416 std::stack<std::pair<BasicBlock*, Value*> > BlockValueStack;
Hal Finkel7e184492014-09-07 20:29:59 +0000417
Sanjay Patel2a385e22015-01-09 16:47:20 +0000418 /// Keeps track of which block-value pairs are in BlockValueStack.
Hans Wennborg45172ac2014-11-25 17:23:05 +0000419 DenseSet<std::pair<BasicBlock*, Value*> > BlockValueSet;
420
Sanjay Patel2a385e22015-01-09 16:47:20 +0000421 /// Push BV onto BlockValueStack unless it's already in there.
422 /// Returns true on success.
Hans Wennborg45172ac2014-11-25 17:23:05 +0000423 bool pushBlockValue(const std::pair<BasicBlock *, Value *> &BV) {
Benjamin Kramer4e3b9032015-02-27 21:43:14 +0000424 if (!BlockValueSet.insert(BV).second)
Hans Wennborg45172ac2014-11-25 17:23:05 +0000425 return false; // It's already in the stack.
426
Philip Reames44456b82016-02-02 03:15:40 +0000427 DEBUG(dbgs() << "PUSH: " << *BV.second << " in " << BV.first->getName()
428 << "\n");
Hans Wennborg45172ac2014-11-25 17:23:05 +0000429 BlockValueStack.push(BV);
Hans Wennborg45172ac2014-11-25 17:23:05 +0000430 return true;
431 }
432
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000433 AssumptionCache *AC; ///< A pointer to the cache of @llvm.assume calls.
434 const DataLayout &DL; ///< A mandatory DataLayout
435 DominatorTree *DT; ///< An optional DT pointer.
436
Owen Anderson118ac802011-01-05 21:15:29 +0000437 friend struct LVIValueHandle;
Owen Anderson6f060af2011-01-05 23:26:22 +0000438
Hans Wennborg45172ac2014-11-25 17:23:05 +0000439 void insertResult(Value *Val, BasicBlock *BB, const LVILatticeVal &Result) {
440 SeenBlocks.insert(BB);
Akira Hatanaka2992bee2015-12-11 00:49:47 +0000441
442 // Insert over-defined values into their own cache to reduce memory
443 // overhead.
Hans Wennborg45172ac2014-11-25 17:23:05 +0000444 if (Result.isOverdefined())
Bruno Cardoso Lopes6ac4ea42015-08-18 16:34:27 +0000445 OverDefinedCache[BB].insert(Val);
Justin Lebar58b377e2016-07-27 22:33:36 +0000446 else {
447 auto It = ValueCache.find_as(Val);
448 if (It == ValueCache.end()) {
449 ValueCache[Val] = make_unique<ValueCacheEntryTy>(Val, this);
450 It = ValueCache.find_as(Val);
451 assert(It != ValueCache.end() && "Val was just added to the map!");
452 }
453 It->second->BlockVals[BB] = Result;
454 }
Hans Wennborg45172ac2014-11-25 17:23:05 +0000455 }
Owen Andersonc1561b82010-07-30 23:59:40 +0000456
NAKAMURA Takumif4c64412016-07-04 01:26:14 +0000457 LVILatticeVal getBlockValue(Value *Val, BasicBlock *BB);
458 bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T,
459 LVILatticeVal &Result, Instruction *CxtI = nullptr);
460 bool hasBlockValue(Value *Val, BasicBlock *BB);
Nick Lewycky55a700b2010-12-18 01:00:40 +0000461
NAKAMURA Takumif4c64412016-07-04 01:26:14 +0000462 // These methods process one work item and may add more. A false value
463 // returned means that the work item was not completely processed and must
464 // be revisited after going through the new items.
465 bool solveBlockValue(Value *Val, BasicBlock *BB);
466 bool solveBlockValueNonLocal(LVILatticeVal &BBLV, Value *Val, BasicBlock *BB);
467 bool solveBlockValuePHINode(LVILatticeVal &BBLV, PHINode *PN, BasicBlock *BB);
468 bool solveBlockValueSelect(LVILatticeVal &BBLV, SelectInst *S,
469 BasicBlock *BB);
470 bool solveBlockValueBinaryOp(LVILatticeVal &BBLV, Instruction *BBI,
471 BasicBlock *BB);
472 bool solveBlockValueCast(LVILatticeVal &BBLV, Instruction *BBI,
473 BasicBlock *BB);
474 void intersectAssumeBlockValueConstantRange(Value *Val, LVILatticeVal &BBLV,
475 Instruction *BBI);
Nick Lewycky55a700b2010-12-18 01:00:40 +0000476
NAKAMURA Takumif4c64412016-07-04 01:26:14 +0000477 void solve();
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000478
Akira Hatanaka2992bee2015-12-11 00:49:47 +0000479 bool isOverdefined(Value *V, BasicBlock *BB) const {
480 auto ODI = OverDefinedCache.find(BB);
481
482 if (ODI == OverDefinedCache.end())
483 return false;
484
485 return ODI->second.count(V);
486 }
487
488 bool hasCachedValueInfo(Value *V, BasicBlock *BB) {
489 if (isOverdefined(V, BB))
490 return true;
491
Justin Lebar58b377e2016-07-27 22:33:36 +0000492 auto I = ValueCache.find_as(V);
Akira Hatanaka2992bee2015-12-11 00:49:47 +0000493 if (I == ValueCache.end())
494 return false;
495
Justin Lebar58b377e2016-07-27 22:33:36 +0000496 return I->second->BlockVals.count(BB);
Akira Hatanaka2992bee2015-12-11 00:49:47 +0000497 }
498
499 LVILatticeVal getCachedValueInfo(Value *V, BasicBlock *BB) {
500 if (isOverdefined(V, BB))
501 return LVILatticeVal::getOverdefined();
502
Justin Lebar58b377e2016-07-27 22:33:36 +0000503 auto I = ValueCache.find_as(V);
504 if (I == ValueCache.end())
505 return LVILatticeVal();
506 auto BBI = I->second->BlockVals.find(BB);
507 if (BBI == I->second->BlockVals.end())
508 return LVILatticeVal();
509 return BBI->second;
Akira Hatanaka2992bee2015-12-11 00:49:47 +0000510 }
NAKAMURA Takumi4cb46e62016-07-04 01:26:33 +0000511
Chris Lattneraf025d32009-11-15 19:59:49 +0000512 public:
Sanjay Patel2a385e22015-01-09 16:47:20 +0000513 /// This is the query interface to determine the lattice
Chris Lattneraf025d32009-11-15 19:59:49 +0000514 /// value for the specified Value* at the end of the specified block.
Hal Finkel7e184492014-09-07 20:29:59 +0000515 LVILatticeVal getValueInBlock(Value *V, BasicBlock *BB,
516 Instruction *CxtI = nullptr);
517
Sanjay Patel2a385e22015-01-09 16:47:20 +0000518 /// This is the query interface to determine the lattice
Hal Finkel7e184492014-09-07 20:29:59 +0000519 /// value for the specified Value* at the specified instruction (generally
520 /// from an assume intrinsic).
521 LVILatticeVal getValueAt(Value *V, Instruction *CxtI);
Chris Lattneraf025d32009-11-15 19:59:49 +0000522
Sanjay Patel2a385e22015-01-09 16:47:20 +0000523 /// This is the query interface to determine the lattice
Chris Lattneraf025d32009-11-15 19:59:49 +0000524 /// value for the specified Value* that is true on the specified edge.
Hal Finkel7e184492014-09-07 20:29:59 +0000525 LVILatticeVal getValueOnEdge(Value *V, BasicBlock *FromBB,BasicBlock *ToBB,
526 Instruction *CxtI = nullptr);
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000527
Sanjay Patel2a385e22015-01-09 16:47:20 +0000528 /// This is the update interface to inform the cache that an edge from
529 /// PredBB to OldSucc has been threaded to be from PredBB to NewSucc.
Owen Andersonaa7f66b2010-07-26 18:48:03 +0000530 void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc);
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000531
Sanjay Patel2a385e22015-01-09 16:47:20 +0000532 /// This is part of the update interface to inform the cache
Owen Anderson208636f2010-08-18 18:39:01 +0000533 /// that a block has been deleted.
534 void eraseBlock(BasicBlock *BB);
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000535
Owen Anderson208636f2010-08-18 18:39:01 +0000536 /// clear - Empty the cache.
537 void clear() {
Benjamin Kramerbbf3c602011-12-03 15:19:55 +0000538 SeenBlocks.clear();
Owen Anderson208636f2010-08-18 18:39:01 +0000539 ValueCache.clear();
540 OverDefinedCache.clear();
541 }
Hal Finkel7e184492014-09-07 20:29:59 +0000542
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000543 LazyValueInfoCache(AssumptionCache *AC, const DataLayout &DL,
Chandler Carruth66b31302015-01-04 12:03:27 +0000544 DominatorTree *DT = nullptr)
545 : AC(AC), DL(DL), DT(DT) {}
Chris Lattneraf025d32009-11-15 19:59:49 +0000546 };
547} // end anonymous namespace
548
Owen Anderson118ac802011-01-05 21:15:29 +0000549void LVIValueHandle::deleted() {
Bruno Cardoso Lopes6ac4ea42015-08-18 16:34:27 +0000550 SmallVector<AssertingVH<BasicBlock>, 4> ToErase;
551 for (auto &I : Parent->OverDefinedCache) {
552 SmallPtrSetImpl<Value *> &ValueSet = I.second;
553 if (ValueSet.count(getValPtr()))
554 ValueSet.erase(getValPtr());
555 if (ValueSet.empty())
556 ToErase.push_back(I.first);
557 }
558 for (auto &BB : ToErase)
559 Parent->OverDefinedCache.erase(BB);
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000560
Owen Anderson7b974a42010-08-11 22:36:04 +0000561 // This erasure deallocates *this, so it MUST happen after we're done
562 // using any and all members of *this.
563 Parent->ValueCache.erase(*this);
Owen Andersonc1561b82010-07-30 23:59:40 +0000564}
565
Owen Anderson208636f2010-08-18 18:39:01 +0000566void LazyValueInfoCache::eraseBlock(BasicBlock *BB) {
Benjamin Kramer36647082011-12-03 15:16:45 +0000567 // Shortcut if we have never seen this block.
568 DenseSet<AssertingVH<BasicBlock> >::iterator I = SeenBlocks.find(BB);
569 if (I == SeenBlocks.end())
570 return;
571 SeenBlocks.erase(I);
572
Bruno Cardoso Lopes6ac4ea42015-08-18 16:34:27 +0000573 auto ODI = OverDefinedCache.find(BB);
574 if (ODI != OverDefinedCache.end())
575 OverDefinedCache.erase(ODI);
Owen Anderson208636f2010-08-18 18:39:01 +0000576
Benjamin Krameraa209152016-06-26 17:27:42 +0000577 for (auto &I : ValueCache)
Justin Lebar58b377e2016-07-27 22:33:36 +0000578 I.second->BlockVals.erase(BB);
Owen Anderson208636f2010-08-18 18:39:01 +0000579}
Owen Andersonc1561b82010-07-30 23:59:40 +0000580
Nick Lewycky55a700b2010-12-18 01:00:40 +0000581void LazyValueInfoCache::solve() {
Owen Anderson6f060af2011-01-05 23:26:22 +0000582 while (!BlockValueStack.empty()) {
583 std::pair<BasicBlock*, Value*> &e = BlockValueStack.top();
Hans Wennborg45172ac2014-11-25 17:23:05 +0000584 assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!");
585
Nuno Lopese6e04902012-06-28 01:16:18 +0000586 if (solveBlockValue(e.second, e.first)) {
Hans Wennborg45172ac2014-11-25 17:23:05 +0000587 // The work item was completely processed.
588 assert(BlockValueStack.top() == e && "Nothing should have been pushed!");
Akira Hatanaka2992bee2015-12-11 00:49:47 +0000589 assert(hasCachedValueInfo(e.second, e.first) &&
590 "Result should be in cache!");
Hans Wennborg45172ac2014-11-25 17:23:05 +0000591
Philip Reames44456b82016-02-02 03:15:40 +0000592 DEBUG(dbgs() << "POP " << *e.second << " in " << e.first->getName()
Philip Reamesb7571042016-02-02 22:43:08 +0000593 << " = " << getCachedValueInfo(e.second, e.first) << "\n");
Philip Reames44456b82016-02-02 03:15:40 +0000594
Owen Anderson6f060af2011-01-05 23:26:22 +0000595 BlockValueStack.pop();
Hans Wennborg45172ac2014-11-25 17:23:05 +0000596 BlockValueSet.erase(e);
597 } else {
598 // More work needs to be done before revisiting.
599 assert(BlockValueStack.top() != e && "Stack should have been pushed!");
Nuno Lopese6e04902012-06-28 01:16:18 +0000600 }
Nick Lewycky55a700b2010-12-18 01:00:40 +0000601 }
602}
603
604bool LazyValueInfoCache::hasBlockValue(Value *Val, BasicBlock *BB) {
605 // If already a constant, there is nothing to compute.
606 if (isa<Constant>(Val))
607 return true;
608
Akira Hatanaka2992bee2015-12-11 00:49:47 +0000609 return hasCachedValueInfo(Val, BB);
Nick Lewycky55a700b2010-12-18 01:00:40 +0000610}
611
Owen Andersonc7ed4dc2010-12-09 06:14:58 +0000612LVILatticeVal LazyValueInfoCache::getBlockValue(Value *Val, BasicBlock *BB) {
Nick Lewycky55a700b2010-12-18 01:00:40 +0000613 // If already a constant, there is nothing to compute.
614 if (Constant *VC = dyn_cast<Constant>(Val))
615 return LVILatticeVal::get(VC);
616
Benjamin Kramer36647082011-12-03 15:16:45 +0000617 SeenBlocks.insert(BB);
Akira Hatanaka2992bee2015-12-11 00:49:47 +0000618 return getCachedValueInfo(Val, BB);
Nick Lewycky55a700b2010-12-18 01:00:40 +0000619}
620
Philip Reameseb3e9da2015-10-29 03:57:17 +0000621static LVILatticeVal getFromRangeMetadata(Instruction *BBI) {
622 switch (BBI->getOpcode()) {
623 default: break;
624 case Instruction::Load:
625 case Instruction::Call:
626 case Instruction::Invoke:
NAKAMURA Takumibd072a92016-07-25 00:59:46 +0000627 if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range))
Philip Reames70efccd2015-10-29 04:21:49 +0000628 if (isa<IntegerType>(BBI->getType())) {
Benjamin Kramer2337c1f2016-02-20 10:40:34 +0000629 return LVILatticeVal::getRange(getConstantRangeFromMetadata(*Ranges));
Philip Reameseb3e9da2015-10-29 03:57:17 +0000630 }
631 break;
632 };
Philip Reamesd1f829d2016-02-02 21:57:37 +0000633 // Nothing known - will be intersected with other facts
634 return LVILatticeVal::getOverdefined();
Philip Reameseb3e9da2015-10-29 03:57:17 +0000635}
636
Nick Lewycky55a700b2010-12-18 01:00:40 +0000637bool LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) {
638 if (isa<Constant>(Val))
639 return true;
640
Akira Hatanaka2992bee2015-12-11 00:49:47 +0000641 if (hasCachedValueInfo(Val, BB)) {
Hans Wennborg45172ac2014-11-25 17:23:05 +0000642 // If we have a cached value, use that.
643 DEBUG(dbgs() << " reuse BB '" << BB->getName()
Akira Hatanaka2992bee2015-12-11 00:49:47 +0000644 << "' val=" << getCachedValueInfo(Val, BB) << '\n');
Nick Lewycky55a700b2010-12-18 01:00:40 +0000645
Hans Wennborg45172ac2014-11-25 17:23:05 +0000646 // Since we're reusing a cached value, we don't need to update the
647 // OverDefinedCache. The cache will have been properly updated whenever the
648 // cached value was inserted.
Nick Lewycky55a700b2010-12-18 01:00:40 +0000649 return true;
Chris Lattner2c708562009-11-15 20:00:52 +0000650 }
651
Hans Wennborg45172ac2014-11-25 17:23:05 +0000652 // Hold off inserting this value into the Cache in case we have to return
653 // false and come back later.
654 LVILatticeVal Res;
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000655
Chris Lattneraf025d32009-11-15 19:59:49 +0000656 Instruction *BBI = dyn_cast<Instruction>(Val);
Craig Topper9f008862014-04-15 04:59:12 +0000657 if (!BBI || BBI->getParent() != BB) {
Hans Wennborg45172ac2014-11-25 17:23:05 +0000658 if (!solveBlockValueNonLocal(Res, Val, BB))
659 return false;
660 insertResult(Val, BB, Res);
661 return true;
Chris Lattneraf025d32009-11-15 19:59:49 +0000662 }
Chris Lattner2c708562009-11-15 20:00:52 +0000663
Nick Lewycky55a700b2010-12-18 01:00:40 +0000664 if (PHINode *PN = dyn_cast<PHINode>(BBI)) {
Hans Wennborg45172ac2014-11-25 17:23:05 +0000665 if (!solveBlockValuePHINode(Res, PN, BB))
666 return false;
667 insertResult(Val, BB, Res);
668 return true;
Nick Lewycky55a700b2010-12-18 01:00:40 +0000669 }
Owen Anderson80d19f02010-08-18 21:11:37 +0000670
Philip Reamesc0bdb0c2016-02-01 22:57:53 +0000671 if (auto *SI = dyn_cast<SelectInst>(BBI)) {
672 if (!solveBlockValueSelect(Res, SI, BB))
673 return false;
674 insertResult(Val, BB, Res);
675 return true;
676 }
677
Philip Reames2ab964e2016-04-27 01:02:25 +0000678 // If this value is a nonnull pointer, record it's range and bailout. Note
679 // that for all other pointer typed values, we terminate the search at the
680 // definition. We could easily extend this to look through geps, bitcasts,
681 // and the like to prove non-nullness, but it's not clear that's worth it
682 // compile time wise. The context-insensative value walk done inside
683 // isKnownNonNull gets most of the profitable cases at much less expense.
684 // This does mean that we have a sensativity to where the defining
685 // instruction is placed, even if it could legally be hoisted much higher.
686 // That is unfortunate.
Igor Laevsky0fa48192015-09-18 13:01:48 +0000687 PointerType *PT = dyn_cast<PointerType>(BBI->getType());
688 if (PT && isKnownNonNull(BBI)) {
689 Res = LVILatticeVal::getNot(ConstantPointerNull::get(PT));
Hans Wennborg45172ac2014-11-25 17:23:05 +0000690 insertResult(Val, BB, Res);
691 return true;
Nick Lewycky367f98f2011-01-15 09:16:12 +0000692 }
Davide Italianobd543d02016-05-25 22:29:34 +0000693 if (BBI->getType()->isIntegerTy()) {
Philip Reames2ab964e2016-04-27 01:02:25 +0000694 if (isa<CastInst>(BBI)) {
695 if (!solveBlockValueCast(Res, BBI, BB))
696 return false;
697 insertResult(Val, BB, Res);
698 return true;
699 }
700 BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI);
NAKAMURA Takumibd072a92016-07-25 00:59:46 +0000701 if (BO && isa<ConstantInt>(BO->getOperand(1))) {
Philip Reames2ab964e2016-04-27 01:02:25 +0000702 if (!solveBlockValueBinaryOp(Res, BBI, BB))
703 return false;
704 insertResult(Val, BB, Res);
705 return true;
706 }
Nick Lewycky55a700b2010-12-18 01:00:40 +0000707 }
Owen Anderson80d19f02010-08-18 21:11:37 +0000708
Philip Reamesa0c9f6e2016-03-04 22:27:39 +0000709 DEBUG(dbgs() << " compute BB '" << BB->getName()
710 << "' - unknown inst def found.\n");
711 Res = getFromRangeMetadata(BBI);
Hans Wennborg45172ac2014-11-25 17:23:05 +0000712 insertResult(Val, BB, Res);
713 return true;
Nick Lewycky55a700b2010-12-18 01:00:40 +0000714}
715
716static bool InstructionDereferencesPointer(Instruction *I, Value *Ptr) {
717 if (LoadInst *L = dyn_cast<LoadInst>(I)) {
718 return L->getPointerAddressSpace() == 0 &&
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000719 GetUnderlyingObject(L->getPointerOperand(),
720 L->getModule()->getDataLayout()) == Ptr;
Nick Lewycky55a700b2010-12-18 01:00:40 +0000721 }
722 if (StoreInst *S = dyn_cast<StoreInst>(I)) {
723 return S->getPointerAddressSpace() == 0 &&
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000724 GetUnderlyingObject(S->getPointerOperand(),
725 S->getModule()->getDataLayout()) == Ptr;
Nick Lewycky55a700b2010-12-18 01:00:40 +0000726 }
Nick Lewycky367f98f2011-01-15 09:16:12 +0000727 if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
728 if (MI->isVolatile()) return false;
Nick Lewycky367f98f2011-01-15 09:16:12 +0000729
730 // FIXME: check whether it has a valuerange that excludes zero?
731 ConstantInt *Len = dyn_cast<ConstantInt>(MI->getLength());
732 if (!Len || Len->isZero()) return false;
733
Eli Friedman7a5fc692011-05-31 20:40:16 +0000734 if (MI->getDestAddressSpace() == 0)
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000735 if (GetUnderlyingObject(MI->getRawDest(),
736 MI->getModule()->getDataLayout()) == Ptr)
Eli Friedman7a5fc692011-05-31 20:40:16 +0000737 return true;
Nick Lewycky367f98f2011-01-15 09:16:12 +0000738 if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI))
Eli Friedman7a5fc692011-05-31 20:40:16 +0000739 if (MTI->getSourceAddressSpace() == 0)
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000740 if (GetUnderlyingObject(MTI->getRawSource(),
741 MTI->getModule()->getDataLayout()) == Ptr)
Eli Friedman7a5fc692011-05-31 20:40:16 +0000742 return true;
Nick Lewycky367f98f2011-01-15 09:16:12 +0000743 }
Nick Lewycky55a700b2010-12-18 01:00:40 +0000744 return false;
745}
746
Philip Reames3f83dbe2016-04-27 00:30:55 +0000747/// Return true if the allocation associated with Val is ever dereferenced
748/// within the given basic block. This establishes the fact Val is not null,
749/// but does not imply that the memory at Val is dereferenceable. (Val may
750/// point off the end of the dereferenceable part of the object.)
751static bool isObjectDereferencedInBlock(Value *Val, BasicBlock *BB) {
752 assert(Val->getType()->isPointerTy());
753
754 const DataLayout &DL = BB->getModule()->getDataLayout();
755 Value *UnderlyingVal = GetUnderlyingObject(Val, DL);
756 // If 'GetUnderlyingObject' didn't converge, skip it. It won't converge
757 // inside InstructionDereferencesPointer either.
758 if (UnderlyingVal == GetUnderlyingObject(UnderlyingVal, DL, 1))
759 for (Instruction &I : *BB)
760 if (InstructionDereferencesPointer(&I, UnderlyingVal))
761 return true;
762 return false;
763}
764
Owen Anderson64c2c572010-12-20 18:18:16 +0000765bool LazyValueInfoCache::solveBlockValueNonLocal(LVILatticeVal &BBLV,
766 Value *Val, BasicBlock *BB) {
Nick Lewycky55a700b2010-12-18 01:00:40 +0000767 LVILatticeVal Result; // Start Undefined.
768
Nick Lewycky55a700b2010-12-18 01:00:40 +0000769 // If this is the entry block, we must be asking about an argument. The
770 // value is overdefined.
771 if (BB == &BB->getParent()->getEntryBlock()) {
772 assert(isa<Argument>(Val) && "Unknown live-in to the entry block");
Philip Reames3f83dbe2016-04-27 00:30:55 +0000773 // Bofore giving up, see if we can prove the pointer non-null local to
774 // this particular block.
775 if (Val->getType()->isPointerTy() &&
776 (isKnownNonNull(Val) || isObjectDereferencedInBlock(Val, BB))) {
Chris Lattner229907c2011-07-18 04:54:35 +0000777 PointerType *PTy = cast<PointerType>(Val->getType());
Nick Lewycky55a700b2010-12-18 01:00:40 +0000778 Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy));
779 } else {
780 Result.markOverdefined();
781 }
Owen Anderson64c2c572010-12-20 18:18:16 +0000782 BBLV = Result;
Nick Lewycky55a700b2010-12-18 01:00:40 +0000783 return true;
784 }
785
786 // Loop over all of our predecessors, merging what we know from them into
787 // result.
788 bool EdgesMissing = false;
Duncan P. N. Exon Smith6c990152014-07-21 17:06:51 +0000789 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
Nick Lewycky55a700b2010-12-18 01:00:40 +0000790 LVILatticeVal EdgeResult;
Duncan P. N. Exon Smith6c990152014-07-21 17:06:51 +0000791 EdgesMissing |= !getEdgeValue(Val, *PI, BB, EdgeResult);
Nick Lewycky55a700b2010-12-18 01:00:40 +0000792 if (EdgesMissing)
793 continue;
794
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000795 Result.mergeIn(EdgeResult, DL);
Nick Lewycky55a700b2010-12-18 01:00:40 +0000796
797 // If we hit overdefined, exit early. The BlockVals entry is already set
798 // to overdefined.
799 if (Result.isOverdefined()) {
800 DEBUG(dbgs() << " compute BB '" << BB->getName()
Philip Reamesb7571042016-02-02 22:43:08 +0000801 << "' - overdefined because of pred (non local).\n");
Philip Reames3f83dbe2016-04-27 00:30:55 +0000802 // Bofore giving up, see if we can prove the pointer non-null local to
803 // this particular block.
804 if (Val->getType()->isPointerTy() &&
805 isObjectDereferencedInBlock(Val, BB)) {
Chris Lattner229907c2011-07-18 04:54:35 +0000806 PointerType *PTy = cast<PointerType>(Val->getType());
Nick Lewycky55a700b2010-12-18 01:00:40 +0000807 Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy));
808 }
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000809
Owen Anderson64c2c572010-12-20 18:18:16 +0000810 BBLV = Result;
Nick Lewycky55a700b2010-12-18 01:00:40 +0000811 return true;
812 }
813 }
814 if (EdgesMissing)
815 return false;
816
817 // Return the merged value, which is more precise than 'overdefined'.
818 assert(!Result.isOverdefined());
Owen Anderson64c2c572010-12-20 18:18:16 +0000819 BBLV = Result;
Nick Lewycky55a700b2010-12-18 01:00:40 +0000820 return true;
821}
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000822
Owen Anderson64c2c572010-12-20 18:18:16 +0000823bool LazyValueInfoCache::solveBlockValuePHINode(LVILatticeVal &BBLV,
824 PHINode *PN, BasicBlock *BB) {
Nick Lewycky55a700b2010-12-18 01:00:40 +0000825 LVILatticeVal Result; // Start Undefined.
826
827 // Loop over all of our predecessors, merging what we know from them into
828 // result.
829 bool EdgesMissing = false;
830 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
831 BasicBlock *PhiBB = PN->getIncomingBlock(i);
832 Value *PhiVal = PN->getIncomingValue(i);
833 LVILatticeVal EdgeResult;
Hal Finkel2400c962014-10-16 00:40:05 +0000834 // Note that we can provide PN as the context value to getEdgeValue, even
835 // though the results will be cached, because PN is the value being used as
836 // the cache key in the caller.
Hal Finkel7e184492014-09-07 20:29:59 +0000837 EdgesMissing |= !getEdgeValue(PhiVal, PhiBB, BB, EdgeResult, PN);
Nick Lewycky55a700b2010-12-18 01:00:40 +0000838 if (EdgesMissing)
839 continue;
840
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000841 Result.mergeIn(EdgeResult, DL);
Nick Lewycky55a700b2010-12-18 01:00:40 +0000842
843 // If we hit overdefined, exit early. The BlockVals entry is already set
844 // to overdefined.
845 if (Result.isOverdefined()) {
846 DEBUG(dbgs() << " compute BB '" << BB->getName()
Philip Reamesb7571042016-02-02 22:43:08 +0000847 << "' - overdefined because of pred (local).\n");
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000848
Owen Anderson64c2c572010-12-20 18:18:16 +0000849 BBLV = Result;
Nick Lewycky55a700b2010-12-18 01:00:40 +0000850 return true;
851 }
852 }
853 if (EdgesMissing)
854 return false;
855
856 // Return the merged value, which is more precise than 'overdefined'.
857 assert(!Result.isOverdefined() && "Possible PHI in entry block?");
Owen Anderson64c2c572010-12-20 18:18:16 +0000858 BBLV = Result;
Nick Lewycky55a700b2010-12-18 01:00:40 +0000859 return true;
860}
861
Artur Pilipenko2e19f592016-08-02 16:20:48 +0000862static bool getValueFromCondition(Value *Val, Value *Cond,
Artur Pilipenko2a8f96f2016-08-02 14:44:32 +0000863 LVILatticeVal &Result,
864 bool isTrueDest = true);
Hal Finkel7e184492014-09-07 20:29:59 +0000865
Philip Reamesd1f829d2016-02-02 21:57:37 +0000866// If we can determine a constraint on the value given conditions assumed by
867// the program, intersect those constraints with BBLV
868void LazyValueInfoCache::intersectAssumeBlockValueConstantRange(Value *Val,
Hans Wennborgc5ec73d2014-11-21 18:58:23 +0000869 LVILatticeVal &BBLV,
870 Instruction *BBI) {
Hal Finkel7e184492014-09-07 20:29:59 +0000871 BBI = BBI ? BBI : dyn_cast<Instruction>(Val);
872 if (!BBI)
873 return;
874
Chandler Carruth66b31302015-01-04 12:03:27 +0000875 for (auto &AssumeVH : AC->assumptions()) {
876 if (!AssumeVH)
877 continue;
878 auto *I = cast<CallInst>(AssumeVH);
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000879 if (!isValidAssumeForContext(I, BBI, DT))
Hal Finkel7e184492014-09-07 20:29:59 +0000880 continue;
881
Artur Pilipenko2e19f592016-08-02 16:20:48 +0000882 LVILatticeVal Result;
883 if (getValueFromCondition(Val, I->getArgOperand(0), Result))
884 BBLV = intersect(BBLV, Result);
Hal Finkel7e184492014-09-07 20:29:59 +0000885 }
886}
887
Philip Reamesc0bdb0c2016-02-01 22:57:53 +0000888bool LazyValueInfoCache::solveBlockValueSelect(LVILatticeVal &BBLV,
889 SelectInst *SI, BasicBlock *BB) {
890
891 // Recurse on our inputs if needed
892 if (!hasBlockValue(SI->getTrueValue(), BB)) {
893 if (pushBlockValue(std::make_pair(BB, SI->getTrueValue())))
894 return false;
895 BBLV.markOverdefined();
896 return true;
897 }
898 LVILatticeVal TrueVal = getBlockValue(SI->getTrueValue(), BB);
899 // If we hit overdefined, don't ask more queries. We want to avoid poisoning
900 // extra slots in the table if we can.
901 if (TrueVal.isOverdefined()) {
902 BBLV.markOverdefined();
903 return true;
904 }
905
906 if (!hasBlockValue(SI->getFalseValue(), BB)) {
907 if (pushBlockValue(std::make_pair(BB, SI->getFalseValue())))
908 return false;
909 BBLV.markOverdefined();
910 return true;
911 }
912 LVILatticeVal FalseVal = getBlockValue(SI->getFalseValue(), BB);
913 // If we hit overdefined, don't ask more queries. We want to avoid poisoning
914 // extra slots in the table if we can.
915 if (FalseVal.isOverdefined()) {
916 BBLV.markOverdefined();
917 return true;
918 }
919
Philip Reamesadf0e352016-02-26 22:53:59 +0000920 if (TrueVal.isConstantRange() && FalseVal.isConstantRange()) {
921 ConstantRange TrueCR = TrueVal.getConstantRange();
922 ConstantRange FalseCR = FalseVal.getConstantRange();
923 Value *LHS = nullptr;
924 Value *RHS = nullptr;
925 SelectPatternResult SPR = matchSelectPattern(SI, LHS, RHS);
926 // Is this a min specifically of our two inputs? (Avoid the risk of
927 // ValueTracking getting smarter looking back past our immediate inputs.)
928 if (SelectPatternResult::isMinOrMax(SPR.Flavor) &&
929 LHS == SI->getTrueValue() && RHS == SI->getFalseValue()) {
930 switch (SPR.Flavor) {
931 default:
932 llvm_unreachable("unexpected minmax type!");
933 case SPF_SMIN: /// Signed minimum
934 BBLV.markConstantRange(TrueCR.smin(FalseCR));
935 return true;
936 case SPF_UMIN: /// Unsigned minimum
937 BBLV.markConstantRange(TrueCR.umin(FalseCR));
938 return true;
939 case SPF_SMAX: /// Signed maximum
940 BBLV.markConstantRange(TrueCR.smax(FalseCR));
941 return true;
NAKAMURA Takumif2529512016-07-04 01:26:27 +0000942 case SPF_UMAX: /// Unsigned maximum
Philip Reamesadf0e352016-02-26 22:53:59 +0000943 BBLV.markConstantRange(TrueCR.umax(FalseCR));
944 return true;
945 };
946 }
NAKAMURA Takumi4cb46e62016-07-04 01:26:33 +0000947
Philip Reamesadf0e352016-02-26 22:53:59 +0000948 // TODO: ABS, NABS from the SelectPatternResult
949 }
950
Philip Reames854a84c2016-02-12 00:09:18 +0000951 // Can we constrain the facts about the true and false values by using the
952 // condition itself? This shows up with idioms like e.g. select(a > 5, a, 5).
953 // TODO: We could potentially refine an overdefined true value above.
Artur Pilipenko2e19f592016-08-02 16:20:48 +0000954 Value *Cond = SI->getCondition();
955 LVILatticeVal TrueValTaken, FalseValTaken;
956 if (!getValueFromCondition(SI->getTrueValue(), Cond, TrueValTaken, true))
957 TrueValTaken.markOverdefined();
958 if (!getValueFromCondition(SI->getFalseValue(), Cond, FalseValTaken, false))
959 FalseValTaken.markOverdefined();
Philip Reames854a84c2016-02-12 00:09:18 +0000960
Artur Pilipenko2e19f592016-08-02 16:20:48 +0000961 TrueVal = intersect(TrueVal, TrueValTaken);
962 FalseVal = intersect(FalseVal, FalseValTaken);
Philip Reames854a84c2016-02-12 00:09:18 +0000963
Artur Pilipenko2e19f592016-08-02 16:20:48 +0000964 // Handle clamp idioms such as:
965 // %24 = constantrange<0, 17>
966 // %39 = icmp eq i32 %24, 0
967 // %40 = add i32 %24, -1
968 // %siv.next = select i1 %39, i32 16, i32 %40
969 // %siv.next = constantrange<0, 17> not <-1, 17>
970 // In general, this can handle any clamp idiom which tests the edge
971 // condition via an equality or inequality.
972 if (auto *ICI = dyn_cast<ICmpInst>(Cond)) {
Philip Reamesadf0e352016-02-26 22:53:59 +0000973 ICmpInst::Predicate Pred = ICI->getPredicate();
974 Value *A = ICI->getOperand(0);
975 if (ConstantInt *CIBase = dyn_cast<ConstantInt>(ICI->getOperand(1))) {
976 auto addConstants = [](ConstantInt *A, ConstantInt *B) {
977 assert(A->getType() == B->getType());
978 return ConstantInt::get(A->getType(), A->getValue() + B->getValue());
979 };
980 // See if either input is A + C2, subject to the constraint from the
981 // condition that A != C when that input is used. We can assume that
982 // that input doesn't include C + C2.
983 ConstantInt *CIAdded;
984 switch (Pred) {
Philip Reames70b39182016-02-27 05:18:30 +0000985 default: break;
Philip Reamesadf0e352016-02-26 22:53:59 +0000986 case ICmpInst::ICMP_EQ:
987 if (match(SI->getFalseValue(), m_Add(m_Specific(A),
988 m_ConstantInt(CIAdded)))) {
989 auto ResNot = addConstants(CIBase, CIAdded);
990 FalseVal = intersect(FalseVal,
991 LVILatticeVal::getNot(ResNot));
992 }
993 break;
994 case ICmpInst::ICMP_NE:
995 if (match(SI->getTrueValue(), m_Add(m_Specific(A),
996 m_ConstantInt(CIAdded)))) {
997 auto ResNot = addConstants(CIBase, CIAdded);
998 TrueVal = intersect(TrueVal,
999 LVILatticeVal::getNot(ResNot));
1000 }
1001 break;
1002 };
1003 }
1004 }
NAKAMURA Takumi4cb46e62016-07-04 01:26:33 +00001005
Philip Reamesc0bdb0c2016-02-01 22:57:53 +00001006 LVILatticeVal Result; // Start Undefined.
1007 Result.mergeIn(TrueVal, DL);
1008 Result.mergeIn(FalseVal, DL);
Philip Reamesc0bdb0c2016-02-01 22:57:53 +00001009 BBLV = Result;
1010 return true;
1011}
1012
Philip Reames66715772016-04-25 18:30:31 +00001013bool LazyValueInfoCache::solveBlockValueCast(LVILatticeVal &BBLV,
1014 Instruction *BBI,
Philip Reamese5030e82016-04-26 22:52:30 +00001015 BasicBlock *BB) {
1016 if (!BBI->getOperand(0)->getType()->isSized()) {
1017 // Without knowing how wide the input is, we can't analyze it in any useful
1018 // way.
1019 BBLV.markOverdefined();
1020 return true;
1021 }
Philip Reamesf105db42016-04-26 23:27:33 +00001022
1023 // Filter out casts we don't know how to reason about before attempting to
1024 // recurse on our operand. This can cut a long search short if we know we're
1025 // not going to be able to get any useful information anways.
1026 switch (BBI->getOpcode()) {
1027 case Instruction::Trunc:
1028 case Instruction::SExt:
1029 case Instruction::ZExt:
1030 case Instruction::BitCast:
1031 break;
1032 default:
1033 // Unhandled instructions are overdefined.
1034 DEBUG(dbgs() << " compute BB '" << BB->getName()
1035 << "' - overdefined (unknown cast).\n");
1036 BBLV.markOverdefined();
1037 return true;
1038 }
1039
Philip Reames38c87c22016-04-26 21:48:16 +00001040 // Figure out the range of the LHS. If that fails, we still apply the
1041 // transfer rule on the full set since we may be able to locally infer
1042 // interesting facts.
1043 if (!hasBlockValue(BBI->getOperand(0), BB))
Hans Wennborg45172ac2014-11-25 17:23:05 +00001044 if (pushBlockValue(std::make_pair(BB, BBI->getOperand(0))))
Philip Reames38c87c22016-04-26 21:48:16 +00001045 // More work to do before applying this transfer rule.
Hans Wennborg45172ac2014-11-25 17:23:05 +00001046 return false;
Philip Reames38c87c22016-04-26 21:48:16 +00001047
1048 const unsigned OperandBitWidth =
Philip Reamese5030e82016-04-26 22:52:30 +00001049 DL.getTypeSizeInBits(BBI->getOperand(0)->getType());
Philip Reames38c87c22016-04-26 21:48:16 +00001050 ConstantRange LHSRange = ConstantRange(OperandBitWidth);
1051 if (hasBlockValue(BBI->getOperand(0), BB)) {
1052 LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB);
1053 intersectAssumeBlockValueConstantRange(BBI->getOperand(0), LHSVal, BBI);
1054 if (LHSVal.isConstantRange())
1055 LHSRange = LHSVal.getConstantRange();
Nick Lewycky55a700b2010-12-18 01:00:40 +00001056 }
1057
Philip Reames38c87c22016-04-26 21:48:16 +00001058 const unsigned ResultBitWidth =
1059 cast<IntegerType>(BBI->getType())->getBitWidth();
Philip Reames66715772016-04-25 18:30:31 +00001060
1061 // NOTE: We're currently limited by the set of operations that ConstantRange
1062 // can evaluate symbolically. Enhancing that set will allows us to analyze
1063 // more definitions.
1064 LVILatticeVal Result;
1065 switch (BBI->getOpcode()) {
1066 case Instruction::Trunc:
Philip Reames38c87c22016-04-26 21:48:16 +00001067 Result.markConstantRange(LHSRange.truncate(ResultBitWidth));
Philip Reames66715772016-04-25 18:30:31 +00001068 break;
1069 case Instruction::SExt:
Philip Reames38c87c22016-04-26 21:48:16 +00001070 Result.markConstantRange(LHSRange.signExtend(ResultBitWidth));
Philip Reames66715772016-04-25 18:30:31 +00001071 break;
1072 case Instruction::ZExt:
Philip Reames38c87c22016-04-26 21:48:16 +00001073 Result.markConstantRange(LHSRange.zeroExtend(ResultBitWidth));
Philip Reames66715772016-04-25 18:30:31 +00001074 break;
1075 case Instruction::BitCast:
1076 Result.markConstantRange(LHSRange);
1077 break;
Philip Reames66715772016-04-25 18:30:31 +00001078 default:
Philip Reamesf105db42016-04-26 23:27:33 +00001079 // Should be dead if the code above is correct
1080 llvm_unreachable("inconsistent with above");
Philip Reames66715772016-04-25 18:30:31 +00001081 break;
Owen Anderson80d19f02010-08-18 21:11:37 +00001082 }
Nick Lewycky55a700b2010-12-18 01:00:40 +00001083
Philip Reames66715772016-04-25 18:30:31 +00001084 BBLV = Result;
1085 return true;
1086}
1087
1088bool LazyValueInfoCache::solveBlockValueBinaryOp(LVILatticeVal &BBLV,
1089 Instruction *BBI,
Philip Reamese5030e82016-04-26 22:52:30 +00001090 BasicBlock *BB) {
Philip Reames66715772016-04-25 18:30:31 +00001091
Philip Reames053c2a62016-04-26 23:10:35 +00001092 assert(BBI->getOperand(0)->getType()->isSized() &&
1093 "all operands to binary operators are sized");
Philip Reamesf105db42016-04-26 23:27:33 +00001094
1095 // Filter out operators we don't know how to reason about before attempting to
1096 // recurse on our operand(s). This can cut a long search short if we know
1097 // we're not going to be able to get any useful information anways.
1098 switch (BBI->getOpcode()) {
1099 case Instruction::Add:
1100 case Instruction::Sub:
1101 case Instruction::Mul:
1102 case Instruction::UDiv:
1103 case Instruction::Shl:
1104 case Instruction::LShr:
1105 case Instruction::And:
1106 case Instruction::Or:
1107 // continue into the code below
1108 break;
1109 default:
1110 // Unhandled instructions are overdefined.
1111 DEBUG(dbgs() << " compute BB '" << BB->getName()
1112 << "' - overdefined (unknown binary operator).\n");
1113 BBLV.markOverdefined();
1114 return true;
1115 };
NAKAMURA Takumi4cb46e62016-07-04 01:26:33 +00001116
Philip Reames053c2a62016-04-26 23:10:35 +00001117 // Figure out the range of the LHS. If that fails, use a conservative range,
1118 // but apply the transfer rule anyways. This lets us pick up facts from
1119 // expressions like "and i32 (call i32 @foo()), 32"
1120 if (!hasBlockValue(BBI->getOperand(0), BB))
1121 if (pushBlockValue(std::make_pair(BB, BBI->getOperand(0))))
1122 // More work to do before applying this transfer rule.
1123 return false;
1124
1125 const unsigned OperandBitWidth =
1126 DL.getTypeSizeInBits(BBI->getOperand(0)->getType());
1127 ConstantRange LHSRange = ConstantRange(OperandBitWidth);
1128 if (hasBlockValue(BBI->getOperand(0), BB)) {
1129 LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB);
1130 intersectAssumeBlockValueConstantRange(BBI->getOperand(0), LHSVal, BBI);
1131 if (LHSVal.isConstantRange())
1132 LHSRange = LHSVal.getConstantRange();
Philip Reames66715772016-04-25 18:30:31 +00001133 }
Philip Reames66715772016-04-25 18:30:31 +00001134
1135 ConstantInt *RHS = cast<ConstantInt>(BBI->getOperand(1));
1136 ConstantRange RHSRange = ConstantRange(RHS->getValue());
1137
Owen Anderson80d19f02010-08-18 21:11:37 +00001138 // NOTE: We're currently limited by the set of operations that ConstantRange
1139 // can evaluate symbolically. Enhancing that set will allows us to analyze
1140 // more definitions.
Owen Anderson64c2c572010-12-20 18:18:16 +00001141 LVILatticeVal Result;
Owen Anderson80d19f02010-08-18 21:11:37 +00001142 switch (BBI->getOpcode()) {
1143 case Instruction::Add:
1144 Result.markConstantRange(LHSRange.add(RHSRange));
1145 break;
1146 case Instruction::Sub:
1147 Result.markConstantRange(LHSRange.sub(RHSRange));
1148 break;
1149 case Instruction::Mul:
1150 Result.markConstantRange(LHSRange.multiply(RHSRange));
1151 break;
1152 case Instruction::UDiv:
1153 Result.markConstantRange(LHSRange.udiv(RHSRange));
1154 break;
1155 case Instruction::Shl:
1156 Result.markConstantRange(LHSRange.shl(RHSRange));
1157 break;
1158 case Instruction::LShr:
1159 Result.markConstantRange(LHSRange.lshr(RHSRange));
1160 break;
Nick Lewyckyad48e012010-09-07 05:39:02 +00001161 case Instruction::And:
1162 Result.markConstantRange(LHSRange.binaryAnd(RHSRange));
1163 break;
1164 case Instruction::Or:
1165 Result.markConstantRange(LHSRange.binaryOr(RHSRange));
1166 break;
Owen Anderson80d19f02010-08-18 21:11:37 +00001167 default:
Philip Reamesf105db42016-04-26 23:27:33 +00001168 // Should be dead if the code above is correct
1169 llvm_unreachable("inconsistent with above");
Owen Anderson80d19f02010-08-18 21:11:37 +00001170 break;
1171 }
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001172
Owen Anderson64c2c572010-12-20 18:18:16 +00001173 BBLV = Result;
Nick Lewycky55a700b2010-12-18 01:00:40 +00001174 return true;
Chris Lattner741c94c2009-11-11 00:22:30 +00001175}
1176
Artur Pilipenko2e19f592016-08-02 16:20:48 +00001177bool getValueFromCondition(Value *Val, Value *Cond, LVILatticeVal &Result,
Artur Pilipenko2a8f96f2016-08-02 14:44:32 +00001178 bool isTrueDest) {
Artur Pilipenko2e19f592016-08-02 16:20:48 +00001179 assert(Cond && "precondition");
1180
1181 // For now we only support ICmpInst conditions
1182 ICmpInst *ICI = dyn_cast<ICmpInst>(Cond);
1183 if (!ICI)
1184 return false;
1185
Philip Reames19183842016-04-25 22:21:24 +00001186 if (isa<Constant>(ICI->getOperand(1))) {
Hal Finkel7e184492014-09-07 20:29:59 +00001187 if (ICI->isEquality() && ICI->getOperand(0) == Val) {
1188 // We know that V has the RHS constant if this is a true SETEQ or
NAKAMURA Takumif2529512016-07-04 01:26:27 +00001189 // false SETNE.
Hal Finkel7e184492014-09-07 20:29:59 +00001190 if (isTrueDest == (ICI->getPredicate() == ICmpInst::ICMP_EQ))
1191 Result = LVILatticeVal::get(cast<Constant>(ICI->getOperand(1)));
1192 else
1193 Result = LVILatticeVal::getNot(cast<Constant>(ICI->getOperand(1)));
1194 return true;
1195 }
1196
1197 // Recognize the range checking idiom that InstCombine produces.
1198 // (X-C1) u< C2 --> [C1, C1+C2)
1199 ConstantInt *NegOffset = nullptr;
1200 if (ICI->getPredicate() == ICmpInst::ICMP_ULT)
1201 match(ICI->getOperand(0), m_Add(m_Specific(Val),
1202 m_ConstantInt(NegOffset)));
1203
1204 ConstantInt *CI = dyn_cast<ConstantInt>(ICI->getOperand(1));
1205 if (CI && (ICI->getOperand(0) == Val || NegOffset)) {
Sanjoy Das7182d362015-03-18 00:41:24 +00001206 // Calculate the range of values that are allowed by the comparison
Hal Finkel7e184492014-09-07 20:29:59 +00001207 ConstantRange CmpRange(CI->getValue());
1208 ConstantRange TrueValues =
Sanjoy Das7182d362015-03-18 00:41:24 +00001209 ConstantRange::makeAllowedICmpRegion(ICI->getPredicate(), CmpRange);
Hal Finkel7e184492014-09-07 20:29:59 +00001210
1211 if (NegOffset) // Apply the offset from above.
1212 TrueValues = TrueValues.subtract(NegOffset->getValue());
1213
1214 // If we're interested in the false dest, invert the condition.
1215 if (!isTrueDest) TrueValues = TrueValues.inverse();
1216
Benjamin Kramer2337c1f2016-02-20 10:40:34 +00001217 Result = LVILatticeVal::getRange(std::move(TrueValues));
Hal Finkel7e184492014-09-07 20:29:59 +00001218 return true;
1219 }
1220 }
NAKAMURA Takumi4cb46e62016-07-04 01:26:33 +00001221
Hal Finkel7e184492014-09-07 20:29:59 +00001222 return false;
1223}
1224
Nuno Lopese6e04902012-06-28 01:16:18 +00001225/// \brief Compute the value of Val on the edge BBFrom -> BBTo. Returns false if
Philip Reames13f73242016-02-01 23:21:11 +00001226/// Val is not constrained on the edge. Result is unspecified if return value
1227/// is false.
Nuno Lopese6e04902012-06-28 01:16:18 +00001228static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
1229 BasicBlock *BBTo, LVILatticeVal &Result) {
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001230 // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
Chris Lattner77358782009-11-15 20:02:12 +00001231 // know that v != 0.
Chris Lattner19019ea2009-11-11 22:48:44 +00001232 if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
1233 // If this is a conditional branch and only one successor goes to BBTo, then
Sanjay Patel938e2792015-01-09 16:35:37 +00001234 // we may be able to infer something from the condition.
Chris Lattner19019ea2009-11-11 22:48:44 +00001235 if (BI->isConditional() &&
1236 BI->getSuccessor(0) != BI->getSuccessor(1)) {
1237 bool isTrueDest = BI->getSuccessor(0) == BBTo;
1238 assert(BI->getSuccessor(!isTrueDest) == BBTo &&
1239 "BBTo isn't a successor of BBFrom");
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001240
Chris Lattner19019ea2009-11-11 22:48:44 +00001241 // If V is the condition of the branch itself, then we know exactly what
1242 // it is.
Nick Lewycky55a700b2010-12-18 01:00:40 +00001243 if (BI->getCondition() == Val) {
1244 Result = LVILatticeVal::get(ConstantInt::get(
Owen Anderson185fe002010-08-10 20:03:09 +00001245 Type::getInt1Ty(Val->getContext()), isTrueDest));
Nick Lewycky55a700b2010-12-18 01:00:40 +00001246 return true;
1247 }
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001248
Chris Lattner19019ea2009-11-11 22:48:44 +00001249 // If the condition of the branch is an equality comparison, we may be
1250 // able to infer the value.
Artur Pilipenko2e19f592016-08-02 16:20:48 +00001251 if (getValueFromCondition(Val, BI->getCondition(), Result, isTrueDest))
1252 return true;
Chris Lattner19019ea2009-11-11 22:48:44 +00001253 }
1254 }
Chris Lattner77358782009-11-15 20:02:12 +00001255
1256 // If the edge was formed by a switch on the value, then we may know exactly
1257 // what it is.
1258 if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
Nuno Lopes8650fb82012-06-28 16:13:37 +00001259 if (SI->getCondition() != Val)
1260 return false;
1261
1262 bool DefaultCase = SI->getDefaultDest() == BBTo;
1263 unsigned BitWidth = Val->getType()->getIntegerBitWidth();
1264 ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/);
1265
Hans Wennborgcbb18e32014-11-21 19:07:46 +00001266 for (SwitchInst::CaseIt i : SI->cases()) {
Nuno Lopes8650fb82012-06-28 16:13:37 +00001267 ConstantRange EdgeVal(i.getCaseValue()->getValue());
Manman Renf3fedb62012-09-05 23:45:58 +00001268 if (DefaultCase) {
1269 // It is possible that the default destination is the destination of
1270 // some cases. There is no need to perform difference for those cases.
1271 if (i.getCaseSuccessor() != BBTo)
1272 EdgesVals = EdgesVals.difference(EdgeVal);
1273 } else if (i.getCaseSuccessor() == BBTo)
Nuno Lopesac593802012-05-18 21:02:10 +00001274 EdgesVals = EdgesVals.unionWith(EdgeVal);
Chris Lattner77358782009-11-15 20:02:12 +00001275 }
Benjamin Kramer2337c1f2016-02-20 10:40:34 +00001276 Result = LVILatticeVal::getRange(std::move(EdgesVals));
Nuno Lopes8650fb82012-06-28 16:13:37 +00001277 return true;
Chris Lattner77358782009-11-15 20:02:12 +00001278 }
Nuno Lopese6e04902012-06-28 01:16:18 +00001279 return false;
1280}
1281
Sanjay Patel938e2792015-01-09 16:35:37 +00001282/// \brief Compute the value of Val on the edge BBFrom -> BBTo or the value at
1283/// the basic block if the edge does not constrain Val.
Nuno Lopese6e04902012-06-28 01:16:18 +00001284bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom,
Hal Finkel7e184492014-09-07 20:29:59 +00001285 BasicBlock *BBTo, LVILatticeVal &Result,
1286 Instruction *CxtI) {
Nuno Lopese6e04902012-06-28 01:16:18 +00001287 // If already a constant, there is nothing to compute.
1288 if (Constant *VC = dyn_cast<Constant>(Val)) {
1289 Result = LVILatticeVal::get(VC);
Nick Lewycky55a700b2010-12-18 01:00:40 +00001290 return true;
1291 }
Nuno Lopese6e04902012-06-28 01:16:18 +00001292
Philip Reames44456b82016-02-02 03:15:40 +00001293 LVILatticeVal LocalResult;
1294 if (!getEdgeValueLocal(Val, BBFrom, BBTo, LocalResult))
1295 // If we couldn't constrain the value on the edge, LocalResult doesn't
1296 // provide any information.
1297 LocalResult.markOverdefined();
NAKAMURA Takumi4cb46e62016-07-04 01:26:33 +00001298
Philip Reames44456b82016-02-02 03:15:40 +00001299 if (hasSingleValue(LocalResult)) {
1300 // Can't get any more precise here
1301 Result = LocalResult;
Nuno Lopese6e04902012-06-28 01:16:18 +00001302 return true;
1303 }
1304
1305 if (!hasBlockValue(Val, BBFrom)) {
Hans Wennborg45172ac2014-11-25 17:23:05 +00001306 if (pushBlockValue(std::make_pair(BBFrom, Val)))
1307 return false;
Philip Reames44456b82016-02-02 03:15:40 +00001308 // No new information.
1309 Result = LocalResult;
Hans Wennborg45172ac2014-11-25 17:23:05 +00001310 return true;
Nuno Lopese6e04902012-06-28 01:16:18 +00001311 }
1312
Philip Reames44456b82016-02-02 03:15:40 +00001313 // Try to intersect ranges of the BB and the constraint on the edge.
1314 LVILatticeVal InBlock = getBlockValue(Val, BBFrom);
Philip Reamesd1f829d2016-02-02 21:57:37 +00001315 intersectAssumeBlockValueConstantRange(Val, InBlock, BBFrom->getTerminator());
Hal Finkel2400c962014-10-16 00:40:05 +00001316 // We can use the context instruction (generically the ultimate instruction
1317 // the calling pass is trying to simplify) here, even though the result of
1318 // this function is generally cached when called from the solve* functions
1319 // (and that cached result might be used with queries using a different
1320 // context instruction), because when this function is called from the solve*
1321 // functions, the context instruction is not provided. When called from
1322 // LazyValueInfoCache::getValueOnEdge, the context instruction is provided,
1323 // but then the result is not cached.
Philip Reamesd1f829d2016-02-02 21:57:37 +00001324 intersectAssumeBlockValueConstantRange(Val, InBlock, CxtI);
Philip Reames44456b82016-02-02 03:15:40 +00001325
1326 Result = intersect(LocalResult, InBlock);
Nuno Lopese6e04902012-06-28 01:16:18 +00001327 return true;
Chris Lattner19019ea2009-11-11 22:48:44 +00001328}
1329
Hal Finkel7e184492014-09-07 20:29:59 +00001330LVILatticeVal LazyValueInfoCache::getValueInBlock(Value *V, BasicBlock *BB,
1331 Instruction *CxtI) {
David Greene37e98092009-12-23 20:43:58 +00001332 DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
Chris Lattneraf025d32009-11-15 19:59:49 +00001333 << BB->getName() << "'\n");
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001334
Hans Wennborg45172ac2014-11-25 17:23:05 +00001335 assert(BlockValueStack.empty() && BlockValueSet.empty());
Philip Reamesbb781b42016-02-10 21:46:32 +00001336 if (!hasBlockValue(V, BB)) {
NAKAMURA Takumibd072a92016-07-25 00:59:46 +00001337 pushBlockValue(std::make_pair(BB, V));
Philip Reamesbb781b42016-02-10 21:46:32 +00001338 solve();
1339 }
Owen Andersonc7ed4dc2010-12-09 06:14:58 +00001340 LVILatticeVal Result = getBlockValue(V, BB);
Philip Reamesd1f829d2016-02-02 21:57:37 +00001341 intersectAssumeBlockValueConstantRange(V, Result, CxtI);
Hal Finkel7e184492014-09-07 20:29:59 +00001342
1343 DEBUG(dbgs() << " Result = " << Result << "\n");
1344 return Result;
1345}
1346
1347LVILatticeVal LazyValueInfoCache::getValueAt(Value *V, Instruction *CxtI) {
1348 DEBUG(dbgs() << "LVI Getting value " << *V << " at '"
1349 << CxtI->getName() << "'\n");
1350
Philip Reamesbb781b42016-02-10 21:46:32 +00001351 if (auto *C = dyn_cast<Constant>(V))
1352 return LVILatticeVal::get(C);
1353
Philip Reamesd1f829d2016-02-02 21:57:37 +00001354 LVILatticeVal Result = LVILatticeVal::getOverdefined();
Philip Reameseb3e9da2015-10-29 03:57:17 +00001355 if (auto *I = dyn_cast<Instruction>(V))
1356 Result = getFromRangeMetadata(I);
Philip Reamesd1f829d2016-02-02 21:57:37 +00001357 intersectAssumeBlockValueConstantRange(V, Result, CxtI);
Philip Reames2c275cc2016-02-02 00:45:30 +00001358
David Greene37e98092009-12-23 20:43:58 +00001359 DEBUG(dbgs() << " Result = " << Result << "\n");
Chris Lattneraf025d32009-11-15 19:59:49 +00001360 return Result;
1361}
Chris Lattner19019ea2009-11-11 22:48:44 +00001362
Chris Lattneraf025d32009-11-15 19:59:49 +00001363LVILatticeVal LazyValueInfoCache::
Hal Finkel7e184492014-09-07 20:29:59 +00001364getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
1365 Instruction *CxtI) {
David Greene37e98092009-12-23 20:43:58 +00001366 DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
Chris Lattneraf025d32009-11-15 19:59:49 +00001367 << FromBB->getName() << "' to '" << ToBB->getName() << "'\n");
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001368
Nick Lewycky55a700b2010-12-18 01:00:40 +00001369 LVILatticeVal Result;
Hal Finkel7e184492014-09-07 20:29:59 +00001370 if (!getEdgeValue(V, FromBB, ToBB, Result, CxtI)) {
Nick Lewycky55a700b2010-12-18 01:00:40 +00001371 solve();
Hal Finkel7e184492014-09-07 20:29:59 +00001372 bool WasFastQuery = getEdgeValue(V, FromBB, ToBB, Result, CxtI);
Nick Lewycky55a700b2010-12-18 01:00:40 +00001373 (void)WasFastQuery;
1374 assert(WasFastQuery && "More work to do after problem solved?");
1375 }
1376
David Greene37e98092009-12-23 20:43:58 +00001377 DEBUG(dbgs() << " Result = " << Result << "\n");
Chris Lattneraf025d32009-11-15 19:59:49 +00001378 return Result;
1379}
1380
Owen Andersonaa7f66b2010-07-26 18:48:03 +00001381void LazyValueInfoCache::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
1382 BasicBlock *NewSucc) {
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001383 // When an edge in the graph has been threaded, values that we could not
1384 // determine a value for before (i.e. were marked overdefined) may be
1385 // possible to solve now. We do NOT try to proactively update these values.
1386 // Instead, we clear their entries from the cache, and allow lazy updating to
1387 // recompute them when needed.
1388
Hans Wennborgc5ec73d2014-11-21 18:58:23 +00001389 // The updating process is fairly simple: we need to drop cached info
Owen Andersonaa7f66b2010-07-26 18:48:03 +00001390 // for all values that were marked overdefined in OldSucc, and for those same
1391 // values in any successor of OldSucc (except NewSucc) in which they were
1392 // also marked overdefined.
1393 std::vector<BasicBlock*> worklist;
1394 worklist.push_back(OldSucc);
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001395
Bruno Cardoso Lopes6ac4ea42015-08-18 16:34:27 +00001396 auto I = OverDefinedCache.find(OldSucc);
1397 if (I == OverDefinedCache.end())
1398 return; // Nothing to process here.
Bruno Cardoso Lopes7a1483e2015-08-21 21:18:26 +00001399 SmallVector<Value *, 4> ValsToClear(I->second.begin(), I->second.end());
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001400
Owen Andersonaa7f66b2010-07-26 18:48:03 +00001401 // Use a worklist to perform a depth-first search of OldSucc's successors.
1402 // NOTE: We do not need a visited list since any blocks we have already
1403 // visited will have had their overdefined markers cleared already, and we
1404 // thus won't loop to their successors.
1405 while (!worklist.empty()) {
1406 BasicBlock *ToUpdate = worklist.back();
1407 worklist.pop_back();
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001408
Owen Andersonaa7f66b2010-07-26 18:48:03 +00001409 // Skip blocks only accessible through NewSucc.
1410 if (ToUpdate == NewSucc) continue;
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001411
Owen Andersonaa7f66b2010-07-26 18:48:03 +00001412 bool changed = false;
Bruno Cardoso Lopes7a1483e2015-08-21 21:18:26 +00001413 for (Value *V : ValsToClear) {
Owen Andersonaa7f66b2010-07-26 18:48:03 +00001414 // If a value was marked overdefined in OldSucc, and is here too...
Bruno Cardoso Lopes6ac4ea42015-08-18 16:34:27 +00001415 auto OI = OverDefinedCache.find(ToUpdate);
1416 if (OI == OverDefinedCache.end())
1417 continue;
1418 SmallPtrSetImpl<Value *> &ValueSet = OI->second;
1419 if (!ValueSet.count(V))
1420 continue;
Owen Andersonaa7f66b2010-07-26 18:48:03 +00001421
Bruno Cardoso Lopes6ac4ea42015-08-18 16:34:27 +00001422 ValueSet.erase(V);
1423 if (ValueSet.empty())
1424 OverDefinedCache.erase(OI);
Owen Andersonaa7f66b2010-07-26 18:48:03 +00001425
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001426 // If we removed anything, then we potentially need to update
Owen Andersonaac5a722010-07-27 23:58:11 +00001427 // blocks successors too.
1428 changed = true;
Owen Andersonaa7f66b2010-07-26 18:48:03 +00001429 }
Nick Lewycky55a700b2010-12-18 01:00:40 +00001430
Owen Andersonaa7f66b2010-07-26 18:48:03 +00001431 if (!changed) continue;
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001432
Owen Andersonaa7f66b2010-07-26 18:48:03 +00001433 worklist.insert(worklist.end(), succ_begin(ToUpdate), succ_end(ToUpdate));
1434 }
1435}
1436
Chris Lattneraf025d32009-11-15 19:59:49 +00001437//===----------------------------------------------------------------------===//
1438// LazyValueInfo Impl
1439//===----------------------------------------------------------------------===//
1440
Sanjay Patel2a385e22015-01-09 16:47:20 +00001441/// This lazily constructs the LazyValueInfoCache.
Chandler Carruth66b31302015-01-04 12:03:27 +00001442static LazyValueInfoCache &getCache(void *&PImpl, AssumptionCache *AC,
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001443 const DataLayout *DL,
Hal Finkel7e184492014-09-07 20:29:59 +00001444 DominatorTree *DT = nullptr) {
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001445 if (!PImpl) {
1446 assert(DL && "getCache() called with a null DataLayout");
1447 PImpl = new LazyValueInfoCache(AC, *DL, DT);
1448 }
Chris Lattneraf025d32009-11-15 19:59:49 +00001449 return *static_cast<LazyValueInfoCache*>(PImpl);
1450}
1451
Sean Silva687019f2016-06-13 22:01:25 +00001452bool LazyValueInfoWrapperPass::runOnFunction(Function &F) {
1453 Info.AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001454 const DataLayout &DL = F.getParent()->getDataLayout();
Hal Finkel7e184492014-09-07 20:29:59 +00001455
1456 DominatorTreeWrapperPass *DTWP =
1457 getAnalysisIfAvailable<DominatorTreeWrapperPass>();
Sean Silva687019f2016-06-13 22:01:25 +00001458 Info.DT = DTWP ? &DTWP->getDomTree() : nullptr;
1459 Info.TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
Chad Rosier43a33062011-12-02 01:26:24 +00001460
Sean Silva687019f2016-06-13 22:01:25 +00001461 if (Info.PImpl)
1462 getCache(Info.PImpl, Info.AC, &DL, Info.DT).clear();
Hal Finkel7e184492014-09-07 20:29:59 +00001463
Owen Anderson208636f2010-08-18 18:39:01 +00001464 // Fully lazy.
1465 return false;
1466}
1467
Sean Silva687019f2016-06-13 22:01:25 +00001468void LazyValueInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
Chad Rosier43a33062011-12-02 01:26:24 +00001469 AU.setPreservesAll();
Chandler Carruth66b31302015-01-04 12:03:27 +00001470 AU.addRequired<AssumptionCacheTracker>();
Chandler Carruthb98f63d2015-01-15 10:41:28 +00001471 AU.addRequired<TargetLibraryInfoWrapperPass>();
Chad Rosier43a33062011-12-02 01:26:24 +00001472}
1473
Sean Silva687019f2016-06-13 22:01:25 +00001474LazyValueInfo &LazyValueInfoWrapperPass::getLVI() { return Info; }
1475
1476LazyValueInfo::~LazyValueInfo() { releaseMemory(); }
1477
Chris Lattneraf025d32009-11-15 19:59:49 +00001478void LazyValueInfo::releaseMemory() {
1479 // If the cache was allocated, free it.
1480 if (PImpl) {
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001481 delete &getCache(PImpl, AC, nullptr);
Craig Topper9f008862014-04-15 04:59:12 +00001482 PImpl = nullptr;
Chris Lattneraf025d32009-11-15 19:59:49 +00001483 }
1484}
1485
Sean Silva687019f2016-06-13 22:01:25 +00001486void LazyValueInfoWrapperPass::releaseMemory() { Info.releaseMemory(); }
1487
1488LazyValueInfo LazyValueAnalysis::run(Function &F, FunctionAnalysisManager &FAM) {
1489 auto &AC = FAM.getResult<AssumptionAnalysis>(F);
1490 auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F);
1491 auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F);
1492
1493 return LazyValueInfo(&AC, &TLI, DT);
1494}
1495
Hal Finkel7e184492014-09-07 20:29:59 +00001496Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB,
1497 Instruction *CxtI) {
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001498 const DataLayout &DL = BB->getModule()->getDataLayout();
Hal Finkel7e184492014-09-07 20:29:59 +00001499 LVILatticeVal Result =
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001500 getCache(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
Chandler Carruth66b31302015-01-04 12:03:27 +00001501
Chris Lattner19019ea2009-11-11 22:48:44 +00001502 if (Result.isConstant())
1503 return Result.getConstant();
Nick Lewycky11678bd2010-12-15 18:57:18 +00001504 if (Result.isConstantRange()) {
Owen Anderson38f6b7f2010-08-27 23:29:38 +00001505 ConstantRange CR = Result.getConstantRange();
1506 if (const APInt *SingleVal = CR.getSingleElement())
1507 return ConstantInt::get(V->getContext(), *SingleVal);
1508 }
Craig Topper9f008862014-04-15 04:59:12 +00001509 return nullptr;
Chris Lattner19019ea2009-11-11 22:48:44 +00001510}
Chris Lattnerfde1f8d2009-11-11 02:08:33 +00001511
John Regehre1c481d2016-05-02 19:58:00 +00001512ConstantRange LazyValueInfo::getConstantRange(Value *V, BasicBlock *BB,
NAKAMURA Takumi940cd932016-07-04 01:26:21 +00001513 Instruction *CxtI) {
John Regehre1c481d2016-05-02 19:58:00 +00001514 assert(V->getType()->isIntegerTy());
1515 unsigned Width = V->getType()->getIntegerBitWidth();
1516 const DataLayout &DL = BB->getModule()->getDataLayout();
1517 LVILatticeVal Result =
1518 getCache(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
1519 assert(!Result.isConstant());
1520 if (Result.isUndefined())
1521 return ConstantRange(Width, /*isFullSet=*/false);
1522 if (Result.isConstantRange())
1523 return Result.getConstantRange();
Davide Italianobd543d02016-05-25 22:29:34 +00001524 return ConstantRange(Width, /*isFullSet=*/true);
John Regehre1c481d2016-05-02 19:58:00 +00001525}
1526
Sanjay Patel2a385e22015-01-09 16:47:20 +00001527/// Determine whether the specified value is known to be a
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001528/// constant on the specified edge. Return null if not.
Chris Lattnerd5e25432009-11-12 01:29:10 +00001529Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
Hal Finkel7e184492014-09-07 20:29:59 +00001530 BasicBlock *ToBB,
1531 Instruction *CxtI) {
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001532 const DataLayout &DL = FromBB->getModule()->getDataLayout();
Hal Finkel7e184492014-09-07 20:29:59 +00001533 LVILatticeVal Result =
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001534 getCache(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
Chandler Carruth66b31302015-01-04 12:03:27 +00001535
Chris Lattnerd5e25432009-11-12 01:29:10 +00001536 if (Result.isConstant())
1537 return Result.getConstant();
Nick Lewycky11678bd2010-12-15 18:57:18 +00001538 if (Result.isConstantRange()) {
Owen Anderson185fe002010-08-10 20:03:09 +00001539 ConstantRange CR = Result.getConstantRange();
1540 if (const APInt *SingleVal = CR.getSingleElement())
1541 return ConstantInt::get(V->getContext(), *SingleVal);
1542 }
Craig Topper9f008862014-04-15 04:59:12 +00001543 return nullptr;
Chris Lattnerd5e25432009-11-12 01:29:10 +00001544}
1545
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001546static LazyValueInfo::Tristate getPredicateResult(unsigned Pred, Constant *C,
1547 LVILatticeVal &Result,
1548 const DataLayout &DL,
1549 TargetLibraryInfo *TLI) {
Hal Finkel7e184492014-09-07 20:29:59 +00001550
Chris Lattner565ee2f2009-11-12 04:36:58 +00001551 // If we know the value is a constant, evaluate the conditional.
Craig Topper9f008862014-04-15 04:59:12 +00001552 Constant *Res = nullptr;
Chris Lattner565ee2f2009-11-12 04:36:58 +00001553 if (Result.isConstant()) {
Rafael Espindola7c68beb2014-02-18 15:33:12 +00001554 Res = ConstantFoldCompareInstOperands(Pred, Result.getConstant(), C, DL,
Chad Rosier43a33062011-12-02 01:26:24 +00001555 TLI);
Nick Lewycky11678bd2010-12-15 18:57:18 +00001556 if (ConstantInt *ResCI = dyn_cast<ConstantInt>(Res))
Hal Finkel7e184492014-09-07 20:29:59 +00001557 return ResCI->isZero() ? LazyValueInfo::False : LazyValueInfo::True;
1558 return LazyValueInfo::Unknown;
Chris Lattneraf025d32009-11-15 19:59:49 +00001559 }
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001560
Owen Anderson185fe002010-08-10 20:03:09 +00001561 if (Result.isConstantRange()) {
Owen Andersonc62f7042010-08-24 07:55:44 +00001562 ConstantInt *CI = dyn_cast<ConstantInt>(C);
Hal Finkel7e184492014-09-07 20:29:59 +00001563 if (!CI) return LazyValueInfo::Unknown;
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001564
Owen Anderson185fe002010-08-10 20:03:09 +00001565 ConstantRange CR = Result.getConstantRange();
1566 if (Pred == ICmpInst::ICMP_EQ) {
1567 if (!CR.contains(CI->getValue()))
Hal Finkel7e184492014-09-07 20:29:59 +00001568 return LazyValueInfo::False;
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001569
Owen Anderson185fe002010-08-10 20:03:09 +00001570 if (CR.isSingleElement() && CR.contains(CI->getValue()))
Hal Finkel7e184492014-09-07 20:29:59 +00001571 return LazyValueInfo::True;
Owen Anderson185fe002010-08-10 20:03:09 +00001572 } else if (Pred == ICmpInst::ICMP_NE) {
1573 if (!CR.contains(CI->getValue()))
Hal Finkel7e184492014-09-07 20:29:59 +00001574 return LazyValueInfo::True;
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001575
Owen Anderson185fe002010-08-10 20:03:09 +00001576 if (CR.isSingleElement() && CR.contains(CI->getValue()))
Hal Finkel7e184492014-09-07 20:29:59 +00001577 return LazyValueInfo::False;
Owen Anderson185fe002010-08-10 20:03:09 +00001578 }
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001579
Owen Anderson185fe002010-08-10 20:03:09 +00001580 // Handle more complex predicates.
Nick Lewycky11678bd2010-12-15 18:57:18 +00001581 ConstantRange TrueValues =
1582 ICmpInst::makeConstantRange((ICmpInst::Predicate)Pred, CI->getValue());
1583 if (TrueValues.contains(CR))
Hal Finkel7e184492014-09-07 20:29:59 +00001584 return LazyValueInfo::True;
Nick Lewycky11678bd2010-12-15 18:57:18 +00001585 if (TrueValues.inverse().contains(CR))
Hal Finkel7e184492014-09-07 20:29:59 +00001586 return LazyValueInfo::False;
1587 return LazyValueInfo::Unknown;
Owen Anderson185fe002010-08-10 20:03:09 +00001588 }
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001589
Chris Lattneraf025d32009-11-15 19:59:49 +00001590 if (Result.isNotConstant()) {
Chris Lattner565ee2f2009-11-12 04:36:58 +00001591 // If this is an equality comparison, we can try to fold it knowing that
1592 // "V != C1".
1593 if (Pred == ICmpInst::ICMP_EQ) {
Sylvestre Ledru91ce36c2012-09-27 10:14:43 +00001594 // !C1 == C -> false iff C1 == C.
Chris Lattner565ee2f2009-11-12 04:36:58 +00001595 Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
Rafael Espindola7c68beb2014-02-18 15:33:12 +00001596 Result.getNotConstant(), C, DL,
Chad Rosier43a33062011-12-02 01:26:24 +00001597 TLI);
Chris Lattner565ee2f2009-11-12 04:36:58 +00001598 if (Res->isNullValue())
Hal Finkel7e184492014-09-07 20:29:59 +00001599 return LazyValueInfo::False;
Chris Lattner565ee2f2009-11-12 04:36:58 +00001600 } else if (Pred == ICmpInst::ICMP_NE) {
Sylvestre Ledru91ce36c2012-09-27 10:14:43 +00001601 // !C1 != C -> true iff C1 == C.
Chris Lattnerb0c0a0d2009-11-15 20:01:24 +00001602 Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
Rafael Espindola7c68beb2014-02-18 15:33:12 +00001603 Result.getNotConstant(), C, DL,
Chad Rosier43a33062011-12-02 01:26:24 +00001604 TLI);
Chris Lattner565ee2f2009-11-12 04:36:58 +00001605 if (Res->isNullValue())
Hal Finkel7e184492014-09-07 20:29:59 +00001606 return LazyValueInfo::True;
Chris Lattner565ee2f2009-11-12 04:36:58 +00001607 }
Hal Finkel7e184492014-09-07 20:29:59 +00001608 return LazyValueInfo::Unknown;
Chris Lattner565ee2f2009-11-12 04:36:58 +00001609 }
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001610
Hal Finkel7e184492014-09-07 20:29:59 +00001611 return LazyValueInfo::Unknown;
1612}
1613
Sanjay Patel2a385e22015-01-09 16:47:20 +00001614/// Determine whether the specified value comparison with a constant is known to
1615/// be true or false on the specified CFG edge. Pred is a CmpInst predicate.
Hal Finkel7e184492014-09-07 20:29:59 +00001616LazyValueInfo::Tristate
1617LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
1618 BasicBlock *FromBB, BasicBlock *ToBB,
1619 Instruction *CxtI) {
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001620 const DataLayout &DL = FromBB->getModule()->getDataLayout();
Hal Finkel7e184492014-09-07 20:29:59 +00001621 LVILatticeVal Result =
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001622 getCache(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
Hal Finkel7e184492014-09-07 20:29:59 +00001623
1624 return getPredicateResult(Pred, C, Result, DL, TLI);
1625}
1626
1627LazyValueInfo::Tristate
1628LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C,
1629 Instruction *CxtI) {
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001630 const DataLayout &DL = CxtI->getModule()->getDataLayout();
1631 LVILatticeVal Result = getCache(PImpl, AC, &DL, DT).getValueAt(V, CxtI);
Philip Reames66ab0f02015-06-16 00:49:59 +00001632 Tristate Ret = getPredicateResult(Pred, C, Result, DL, TLI);
1633 if (Ret != Unknown)
1634 return Ret;
Hal Finkel7e184492014-09-07 20:29:59 +00001635
Philip Reamesaeefae02015-11-04 01:47:04 +00001636 // Note: The following bit of code is somewhat distinct from the rest of LVI;
1637 // LVI as a whole tries to compute a lattice value which is conservatively
1638 // correct at a given location. In this case, we have a predicate which we
1639 // weren't able to prove about the merged result, and we're pushing that
1640 // predicate back along each incoming edge to see if we can prove it
1641 // separately for each input. As a motivating example, consider:
1642 // bb1:
1643 // %v1 = ... ; constantrange<1, 5>
1644 // br label %merge
1645 // bb2:
1646 // %v2 = ... ; constantrange<10, 20>
1647 // br label %merge
1648 // merge:
1649 // %phi = phi [%v1, %v2] ; constantrange<1,20>
1650 // %pred = icmp eq i32 %phi, 8
1651 // We can't tell from the lattice value for '%phi' that '%pred' is false
1652 // along each path, but by checking the predicate over each input separately,
1653 // we can.
1654 // We limit the search to one step backwards from the current BB and value.
1655 // We could consider extending this to search further backwards through the
1656 // CFG and/or value graph, but there are non-obvious compile time vs quality
NAKAMURA Takumif2529512016-07-04 01:26:27 +00001657 // tradeoffs.
Philip Reames66ab0f02015-06-16 00:49:59 +00001658 if (CxtI) {
Philip Reamesbb11d622015-08-31 18:31:48 +00001659 BasicBlock *BB = CxtI->getParent();
1660
1661 // Function entry or an unreachable block. Bail to avoid confusing
1662 // analysis below.
1663 pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1664 if (PI == PE)
1665 return Unknown;
1666
1667 // If V is a PHI node in the same block as the context, we need to ask
1668 // questions about the predicate as applied to the incoming value along
1669 // each edge. This is useful for eliminating cases where the predicate is
1670 // known along all incoming edges.
1671 if (auto *PHI = dyn_cast<PHINode>(V))
1672 if (PHI->getParent() == BB) {
1673 Tristate Baseline = Unknown;
1674 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i < e; i++) {
1675 Value *Incoming = PHI->getIncomingValue(i);
1676 BasicBlock *PredBB = PHI->getIncomingBlock(i);
NAKAMURA Takumif2529512016-07-04 01:26:27 +00001677 // Note that PredBB may be BB itself.
Philip Reamesbb11d622015-08-31 18:31:48 +00001678 Tristate Result = getPredicateOnEdge(Pred, Incoming, C, PredBB, BB,
1679 CxtI);
NAKAMURA Takumi4cb46e62016-07-04 01:26:33 +00001680
Philip Reamesbb11d622015-08-31 18:31:48 +00001681 // Keep going as long as we've seen a consistent known result for
1682 // all inputs.
1683 Baseline = (i == 0) ? Result /* First iteration */
1684 : (Baseline == Result ? Baseline : Unknown); /* All others */
1685 if (Baseline == Unknown)
1686 break;
1687 }
1688 if (Baseline != Unknown)
1689 return Baseline;
NAKAMURA Takumibd072a92016-07-25 00:59:46 +00001690 }
Philip Reamesbb11d622015-08-31 18:31:48 +00001691
Philip Reames66ab0f02015-06-16 00:49:59 +00001692 // For a comparison where the V is outside this block, it's possible
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001693 // that we've branched on it before. Look to see if the value is known
Philip Reames66ab0f02015-06-16 00:49:59 +00001694 // on all incoming edges.
Philip Reamesbb11d622015-08-31 18:31:48 +00001695 if (!isa<Instruction>(V) ||
1696 cast<Instruction>(V)->getParent() != BB) {
Philip Reames66ab0f02015-06-16 00:49:59 +00001697 // For predecessor edge, determine if the comparison is true or false
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001698 // on that edge. If they're all true or all false, we can conclude
Philip Reames66ab0f02015-06-16 00:49:59 +00001699 // the value of the comparison in this block.
1700 Tristate Baseline = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1701 if (Baseline != Unknown) {
1702 // Check that all remaining incoming values match the first one.
1703 while (++PI != PE) {
1704 Tristate Ret = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1705 if (Ret != Baseline) break;
1706 }
1707 // If we terminated early, then one of the values didn't match.
1708 if (PI == PE) {
1709 return Baseline;
1710 }
1711 }
1712 }
1713 }
1714 return Unknown;
Chris Lattnerfde1f8d2009-11-11 02:08:33 +00001715}
1716
Owen Andersonaa7f66b2010-07-26 18:48:03 +00001717void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
Nick Lewycky11678bd2010-12-15 18:57:18 +00001718 BasicBlock *NewSucc) {
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001719 if (PImpl) {
1720 const DataLayout &DL = PredBB->getModule()->getDataLayout();
1721 getCache(PImpl, AC, &DL, DT).threadEdge(PredBB, OldSucc, NewSucc);
1722 }
Owen Anderson208636f2010-08-18 18:39:01 +00001723}
1724
1725void LazyValueInfo::eraseBlock(BasicBlock *BB) {
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001726 if (PImpl) {
1727 const DataLayout &DL = BB->getModule()->getDataLayout();
1728 getCache(PImpl, AC, &DL, DT).eraseBlock(BB);
1729 }
Owen Andersonaa7f66b2010-07-26 18:48:03 +00001730}