blob: 0e8ad93fe9bb39603d9f1dbf1d339d435985b55f [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
Chris Lattner741c94c2009-11-11 00:22:30 +000041char LazyValueInfo::ID = 0;
Chad Rosier43a33062011-12-02 01:26:24 +000042INITIALIZE_PASS_BEGIN(LazyValueInfo, "lazy-value-info",
43 "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)
Chad Rosier43a33062011-12-02 01:26:24 +000046INITIALIZE_PASS_END(LazyValueInfo, "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 {
50 FunctionPass *createLazyValueInfoPass() { return new LazyValueInfo(); }
51}
52
Chris Lattnerfde1f8d2009-11-11 02:08:33 +000053
54//===----------------------------------------------------------------------===//
55// LVILatticeVal
56//===----------------------------------------------------------------------===//
57
Sanjay Patel2a385e22015-01-09 16:47:20 +000058/// This is the information tracked by LazyValueInfo for each value.
Chris Lattnerfde1f8d2009-11-11 02:08:33 +000059///
60/// FIXME: This is basically just for bringup, this can be made a lot more rich
61/// in the future.
62///
63namespace {
64class LVILatticeVal {
65 enum LatticeValueTy {
Philip Reames3bb28322016-04-25 18:48:43 +000066 /// This Value has no known value yet. As a result, this implies the
67 /// producing instruction is dead. Caution: We use this as the starting
68 /// state in our local meet rules. In this usage, it's taken to mean
69 /// "nothing known yet".
Chris Lattnerfde1f8d2009-11-11 02:08:33 +000070 undefined,
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +000071
Philip Reames3bb28322016-04-25 18:48:43 +000072 /// This Value has a specific constant value. (For integers, constantrange
73 /// is used instead.)
Chris Lattnerfde1f8d2009-11-11 02:08:33 +000074 constant,
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +000075
Philip Reames3bb28322016-04-25 18:48:43 +000076 /// This Value is known to not have the specified value. (For integers,
77 /// constantrange is used instead.)
Chris Lattner565ee2f2009-11-12 04:36:58 +000078 notconstant,
Chad Rosier43a33062011-12-02 01:26:24 +000079
Philip Reames3bb28322016-04-25 18:48:43 +000080 /// The Value falls within this range. (Used only for integer typed values.)
Owen Anderson0f306a42010-08-05 22:59:19 +000081 constantrange,
Chad Rosier43a33062011-12-02 01:26:24 +000082
Philip Reames3bb28322016-04-25 18:48:43 +000083 /// We can not precisely model the dynamic values this value might take.
Chris Lattnerfde1f8d2009-11-11 02:08:33 +000084 overdefined
85 };
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +000086
Chris Lattnerfde1f8d2009-11-11 02:08:33 +000087 /// Val: This stores the current lattice value along with the Constant* for
Chris Lattner565ee2f2009-11-12 04:36:58 +000088 /// the constant if this is a 'constant' or 'notconstant' value.
Owen Andersonc3a14132010-08-05 22:10:46 +000089 LatticeValueTy Tag;
90 Constant *Val;
Owen Anderson0f306a42010-08-05 22:59:19 +000091 ConstantRange Range;
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +000092
Chris Lattnerfde1f8d2009-11-11 02:08:33 +000093public:
Craig Topper9f008862014-04-15 04:59:12 +000094 LVILatticeVal() : Tag(undefined), Val(nullptr), Range(1, true) {}
Chris Lattnerfde1f8d2009-11-11 02:08:33 +000095
Chris Lattner19019ea2009-11-11 22:48:44 +000096 static LVILatticeVal get(Constant *C) {
97 LVILatticeVal Res;
Nick Lewycky11678bd2010-12-15 18:57:18 +000098 if (!isa<UndefValue>(C))
Owen Anderson185fe002010-08-10 20:03:09 +000099 Res.markConstant(C);
Chris Lattner19019ea2009-11-11 22:48:44 +0000100 return Res;
101 }
Chris Lattner565ee2f2009-11-12 04:36:58 +0000102 static LVILatticeVal getNot(Constant *C) {
103 LVILatticeVal Res;
Nick Lewycky11678bd2010-12-15 18:57:18 +0000104 if (!isa<UndefValue>(C))
Owen Anderson185fe002010-08-10 20:03:09 +0000105 Res.markNotConstant(C);
Chris Lattner565ee2f2009-11-12 04:36:58 +0000106 return Res;
107 }
Owen Anderson5f1dd092010-08-10 23:20:01 +0000108 static LVILatticeVal getRange(ConstantRange CR) {
109 LVILatticeVal Res;
Benjamin Kramer2337c1f2016-02-20 10:40:34 +0000110 Res.markConstantRange(std::move(CR));
Owen Anderson5f1dd092010-08-10 23:20:01 +0000111 return Res;
112 }
Akira Hatanaka2992bee2015-12-11 00:49:47 +0000113 static LVILatticeVal getOverdefined() {
114 LVILatticeVal Res;
115 Res.markOverdefined();
116 return Res;
117 }
118
Owen Anderson0f306a42010-08-05 22:59:19 +0000119 bool isUndefined() const { return Tag == undefined; }
120 bool isConstant() const { return Tag == constant; }
121 bool isNotConstant() const { return Tag == notconstant; }
122 bool isConstantRange() const { return Tag == constantrange; }
123 bool isOverdefined() const { return Tag == overdefined; }
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000124
Chris Lattnerfde1f8d2009-11-11 02:08:33 +0000125 Constant *getConstant() const {
126 assert(isConstant() && "Cannot get the constant of a non-constant!");
Owen Andersonc3a14132010-08-05 22:10:46 +0000127 return Val;
Chris Lattnerfde1f8d2009-11-11 02:08:33 +0000128 }
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000129
Chris Lattner565ee2f2009-11-12 04:36:58 +0000130 Constant *getNotConstant() const {
131 assert(isNotConstant() && "Cannot get the constant of a non-notconstant!");
Owen Andersonc3a14132010-08-05 22:10:46 +0000132 return Val;
Chris Lattnerfde1f8d2009-11-11 02:08:33 +0000133 }
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000134
Owen Anderson0f306a42010-08-05 22:59:19 +0000135 ConstantRange getConstantRange() const {
136 assert(isConstantRange() &&
137 "Cannot get the constant-range of a non-constant-range!");
138 return Range;
139 }
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000140
Sanjay Patel2a385e22015-01-09 16:47:20 +0000141 /// Return true if this is a change in status.
Chris Lattnerfde1f8d2009-11-11 02:08:33 +0000142 bool markOverdefined() {
143 if (isOverdefined())
144 return false;
Owen Andersonc3a14132010-08-05 22:10:46 +0000145 Tag = overdefined;
Chris Lattnerfde1f8d2009-11-11 02:08:33 +0000146 return true;
147 }
148
Sanjay Patel2a385e22015-01-09 16:47:20 +0000149 /// Return true if this is a change in status.
Chris Lattnerfde1f8d2009-11-11 02:08:33 +0000150 bool markConstant(Constant *V) {
Nick Lewycky11678bd2010-12-15 18:57:18 +0000151 assert(V && "Marking constant with NULL");
152 if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
153 return markConstantRange(ConstantRange(CI->getValue()));
154 if (isa<UndefValue>(V))
Chris Lattnerfde1f8d2009-11-11 02:08:33 +0000155 return false;
Nick Lewycky11678bd2010-12-15 18:57:18 +0000156
157 assert((!isConstant() || getConstant() == V) &&
158 "Marking constant with different value");
Chris Lattnerfde1f8d2009-11-11 02:08:33 +0000159 assert(isUndefined());
Owen Andersonc3a14132010-08-05 22:10:46 +0000160 Tag = constant;
Owen Andersonc3a14132010-08-05 22:10:46 +0000161 Val = V;
Chris Lattner19019ea2009-11-11 22:48:44 +0000162 return true;
163 }
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000164
Sanjay Patel2a385e22015-01-09 16:47:20 +0000165 /// Return true if this is a change in status.
Chris Lattner565ee2f2009-11-12 04:36:58 +0000166 bool markNotConstant(Constant *V) {
Chris Lattner565ee2f2009-11-12 04:36:58 +0000167 assert(V && "Marking constant with NULL");
Nick Lewycky11678bd2010-12-15 18:57:18 +0000168 if (ConstantInt *CI = dyn_cast<ConstantInt>(V))
169 return markConstantRange(ConstantRange(CI->getValue()+1, CI->getValue()));
170 if (isa<UndefValue>(V))
171 return false;
172
173 assert((!isConstant() || getConstant() != V) &&
174 "Marking constant !constant with same value");
175 assert((!isNotConstant() || getNotConstant() == V) &&
176 "Marking !constant with different value");
177 assert(isUndefined() || isConstant());
178 Tag = notconstant;
Owen Andersonc3a14132010-08-05 22:10:46 +0000179 Val = V;
Chris Lattner565ee2f2009-11-12 04:36:58 +0000180 return true;
181 }
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000182
Sanjay Patel2a385e22015-01-09 16:47:20 +0000183 /// Return true if this is a change in status.
Benjamin Kramer2337c1f2016-02-20 10:40:34 +0000184 bool markConstantRange(ConstantRange NewR) {
Owen Anderson0f306a42010-08-05 22:59:19 +0000185 if (isConstantRange()) {
186 if (NewR.isEmptySet())
187 return markOverdefined();
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000188
Nuno Lopese6e04902012-06-28 01:16:18 +0000189 bool changed = Range != NewR;
Benjamin Kramer2337c1f2016-02-20 10:40:34 +0000190 Range = std::move(NewR);
Owen Anderson0f306a42010-08-05 22:59:19 +0000191 return changed;
192 }
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000193
Owen Anderson0f306a42010-08-05 22:59:19 +0000194 assert(isUndefined());
195 if (NewR.isEmptySet())
196 return markOverdefined();
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000197
Owen Anderson0f306a42010-08-05 22:59:19 +0000198 Tag = constantrange;
Benjamin Kramer2337c1f2016-02-20 10:40:34 +0000199 Range = std::move(NewR);
Owen Anderson0f306a42010-08-05 22:59:19 +0000200 return true;
201 }
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000202
Sanjay Patel2a385e22015-01-09 16:47:20 +0000203 /// Merge the specified lattice value into this one, updating this
Chris Lattner19019ea2009-11-11 22:48:44 +0000204 /// one and returning true if anything changed.
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000205 bool mergeIn(const LVILatticeVal &RHS, const DataLayout &DL) {
Chris Lattner19019ea2009-11-11 22:48:44 +0000206 if (RHS.isUndefined() || isOverdefined()) return false;
207 if (RHS.isOverdefined()) return markOverdefined();
208
Nick Lewycky11678bd2010-12-15 18:57:18 +0000209 if (isUndefined()) {
210 Tag = RHS.Tag;
211 Val = RHS.Val;
212 Range = RHS.Range;
213 return true;
Chris Lattner22db4b52009-11-12 04:57:13 +0000214 }
215
Nick Lewycky11678bd2010-12-15 18:57:18 +0000216 if (isConstant()) {
217 if (RHS.isConstant()) {
218 if (Val == RHS.Val)
219 return false;
220 return markOverdefined();
221 }
222
223 if (RHS.isNotConstant()) {
224 if (Val == RHS.Val)
225 return markOverdefined();
226
227 // Unless we can prove that the two Constants are different, we must
228 // move to overdefined.
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000229 if (ConstantInt *Res =
230 dyn_cast<ConstantInt>(ConstantFoldCompareInstOperands(
231 CmpInst::ICMP_NE, getConstant(), RHS.getNotConstant(), DL)))
Nick Lewycky11678bd2010-12-15 18:57:18 +0000232 if (Res->isOne())
233 return markNotConstant(RHS.getNotConstant());
234
235 return markOverdefined();
236 }
237
238 // RHS is a ConstantRange, LHS is a non-integer Constant.
239
240 // FIXME: consider the case where RHS is a range [1, 0) and LHS is
241 // a function. The correct result is to pick up RHS.
242
Chris Lattner19019ea2009-11-11 22:48:44 +0000243 return markOverdefined();
Nick Lewycky11678bd2010-12-15 18:57:18 +0000244 }
245
246 if (isNotConstant()) {
247 if (RHS.isConstant()) {
248 if (Val == RHS.Val)
249 return markOverdefined();
250
251 // Unless we can prove that the two Constants are different, we must
252 // move to overdefined.
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000253 if (ConstantInt *Res =
254 dyn_cast<ConstantInt>(ConstantFoldCompareInstOperands(
255 CmpInst::ICMP_NE, getNotConstant(), RHS.getConstant(), DL)))
Nick Lewycky11678bd2010-12-15 18:57:18 +0000256 if (Res->isOne())
257 return false;
258
259 return markOverdefined();
260 }
261
262 if (RHS.isNotConstant()) {
263 if (Val == RHS.Val)
264 return false;
265 return markOverdefined();
266 }
267
268 return markOverdefined();
269 }
270
271 assert(isConstantRange() && "New LVILattice type?");
272 if (!RHS.isConstantRange())
273 return markOverdefined();
274
275 ConstantRange NewR = Range.unionWith(RHS.getConstantRange());
276 if (NewR.isFullSet())
277 return markOverdefined();
278 return markConstantRange(NewR);
Chris Lattnerfde1f8d2009-11-11 02:08:33 +0000279 }
Chris Lattnerfde1f8d2009-11-11 02:08:33 +0000280};
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000281
Chris Lattnerfde1f8d2009-11-11 02:08:33 +0000282} // end anonymous namespace.
283
Chris Lattner19019ea2009-11-11 22:48:44 +0000284namespace llvm {
Chandler Carruth2b1ba482011-04-18 18:49:44 +0000285raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val)
286 LLVM_ATTRIBUTE_USED;
Chris Lattner19019ea2009-11-11 22:48:44 +0000287raw_ostream &operator<<(raw_ostream &OS, const LVILatticeVal &Val) {
288 if (Val.isUndefined())
289 return OS << "undefined";
290 if (Val.isOverdefined())
291 return OS << "overdefined";
Chris Lattner565ee2f2009-11-12 04:36:58 +0000292
293 if (Val.isNotConstant())
294 return OS << "notconstant<" << *Val.getNotConstant() << '>';
Owen Anderson8afac042010-08-09 20:50:46 +0000295 else if (Val.isConstantRange())
296 return OS << "constantrange<" << Val.getConstantRange().getLower() << ", "
297 << Val.getConstantRange().getUpper() << '>';
Chris Lattner19019ea2009-11-11 22:48:44 +0000298 return OS << "constant<" << *Val.getConstant() << '>';
299}
Alexander Kornienkof00654e2015-06-23 09:49:53 +0000300}
Chris Lattnerfde1f8d2009-11-11 02:08:33 +0000301
Philip Reamesed8cd0d2016-02-02 22:03:19 +0000302/// Returns true if this lattice value represents at most one possible value.
303/// This is as precise as any lattice value can get while still representing
304/// reachable code.
305static bool hasSingleValue(LVILatticeVal Val) {
306 if (Val.isConstantRange() &&
307 Val.getConstantRange().isSingleElement())
308 // Integer constants are single element ranges
309 return true;
310 if (Val.isConstant())
311 // Non integer constants
312 return true;
313 return false;
314}
315
316/// Combine two sets of facts about the same value into a single set of
317/// facts. Note that this method is not suitable for merging facts along
318/// different paths in a CFG; that's what the mergeIn function is for. This
319/// is for merging facts gathered about the same value at the same location
320/// through two independent means.
321/// Notes:
322/// * This method does not promise to return the most precise possible lattice
323/// value implied by A and B. It is allowed to return any lattice element
324/// which is at least as strong as *either* A or B (unless our facts
325/// conflict, see below).
326/// * Due to unreachable code, the intersection of two lattice values could be
327/// contradictory. If this happens, we return some valid lattice value so as
328/// not confuse the rest of LVI. Ideally, we'd always return Undefined, but
329/// we do not make this guarantee. TODO: This would be a useful enhancement.
330static LVILatticeVal intersect(LVILatticeVal A, LVILatticeVal B) {
331 // Undefined is the strongest state. It means the value is known to be along
332 // an unreachable path.
333 if (A.isUndefined())
334 return A;
335 if (B.isUndefined())
336 return B;
337
338 // If we gave up for one, but got a useable fact from the other, use it.
339 if (A.isOverdefined())
340 return B;
341 if (B.isOverdefined())
342 return A;
343
344 // Can't get any more precise than constants.
345 if (hasSingleValue(A))
346 return A;
347 if (hasSingleValue(B))
348 return B;
349
350 // Could be either constant range or not constant here.
351 if (!A.isConstantRange() || !B.isConstantRange()) {
352 // TODO: Arbitrary choice, could be improved
353 return A;
354 }
355
356 // Intersect two constant ranges
357 ConstantRange Range =
358 A.getConstantRange().intersectWith(B.getConstantRange());
359 // Note: An empty range is implicitly converted to overdefined internally.
360 // TODO: We could instead use Undefined here since we've proven a conflict
361 // and thus know this path must be unreachable.
Benjamin Kramer2337c1f2016-02-20 10:40:34 +0000362 return LVILatticeVal::getRange(std::move(Range));
Philip Reamesed8cd0d2016-02-02 22:03:19 +0000363}
Philip Reamesd1f829d2016-02-02 21:57:37 +0000364
Chris Lattnerfde1f8d2009-11-11 02:08:33 +0000365//===----------------------------------------------------------------------===//
Chris Lattneraf025d32009-11-15 19:59:49 +0000366// LazyValueInfoCache Decl
Chris Lattnerfde1f8d2009-11-11 02:08:33 +0000367//===----------------------------------------------------------------------===//
368
Chris Lattneraf025d32009-11-15 19:59:49 +0000369namespace {
Sanjay Patel2a385e22015-01-09 16:47:20 +0000370 /// A callback value handle updates the cache when values are erased.
Owen Anderson118ac802011-01-05 21:15:29 +0000371 class LazyValueInfoCache;
David Blaikie774b5842015-08-03 22:30:24 +0000372 struct LVIValueHandle final : public CallbackVH {
Owen Anderson118ac802011-01-05 21:15:29 +0000373 LazyValueInfoCache *Parent;
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000374
Owen Anderson118ac802011-01-05 21:15:29 +0000375 LVIValueHandle(Value *V, LazyValueInfoCache *P)
376 : CallbackVH(V), Parent(P) { }
Craig Toppere9ba7592014-03-05 07:30:04 +0000377
378 void deleted() override;
379 void allUsesReplacedWith(Value *V) override {
Owen Anderson118ac802011-01-05 21:15:29 +0000380 deleted();
381 }
382 };
Alexander Kornienkof00654e2015-06-23 09:49:53 +0000383}
Owen Anderson118ac802011-01-05 21:15:29 +0000384
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000385namespace {
Sanjay Patel2a385e22015-01-09 16:47:20 +0000386 /// This is the cache kept by LazyValueInfo which
Chris Lattneraf025d32009-11-15 19:59:49 +0000387 /// maintains information about queries across the clients' queries.
388 class LazyValueInfoCache {
Sanjay Patel2a385e22015-01-09 16:47:20 +0000389 /// This is all of the cached block information for exactly one Value*.
390 /// The entries are sorted by the BasicBlock* of the
Chris Lattneraf025d32009-11-15 19:59:49 +0000391 /// entries, allowing us to do a lookup with a binary search.
Akira Hatanaka2992bee2015-12-11 00:49:47 +0000392 /// Over-defined lattice values are recorded in OverDefinedCache to reduce
393 /// memory overhead.
Bruno Cardoso Lopes1846ea32015-08-18 16:54:36 +0000394 typedef SmallDenseMap<AssertingVH<BasicBlock>, LVILatticeVal, 4>
395 ValueCacheEntryTy;
Chris Lattneraf025d32009-11-15 19:59:49 +0000396
Sanjay Patel2a385e22015-01-09 16:47:20 +0000397 /// This is all of the cached information for all values,
Owen Anderson6f060af2011-01-05 23:26:22 +0000398 /// mapped from Value* to key information.
Bill Wendling58c75692012-01-12 01:41:03 +0000399 std::map<LVIValueHandle, ValueCacheEntryTy> ValueCache;
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000400
Sanjay Patel2a385e22015-01-09 16:47:20 +0000401 /// This tracks, on a per-block basis, the set of values that are
Akira Hatanaka2992bee2015-12-11 00:49:47 +0000402 /// over-defined at the end of that block.
Bruno Cardoso Lopes6ac4ea42015-08-18 16:34:27 +0000403 typedef DenseMap<AssertingVH<BasicBlock>, SmallPtrSet<Value *, 4>>
404 OverDefinedCacheTy;
405 OverDefinedCacheTy OverDefinedCache;
Benjamin Kramer36647082011-12-03 15:16:45 +0000406
Sanjay Patel2a385e22015-01-09 16:47:20 +0000407 /// Keep track of all blocks that we have ever seen, so we
Benjamin Kramer36647082011-12-03 15:16:45 +0000408 /// don't spend time removing unused blocks from our caches.
409 DenseSet<AssertingVH<BasicBlock> > SeenBlocks;
410
Sanjay Patel2a385e22015-01-09 16:47:20 +0000411 /// This stack holds the state of the value solver during a query.
412 /// It basically emulates the callstack of the naive
Owen Anderson6f060af2011-01-05 23:26:22 +0000413 /// recursive value lookup process.
414 std::stack<std::pair<BasicBlock*, Value*> > BlockValueStack;
Hal Finkel7e184492014-09-07 20:29:59 +0000415
Sanjay Patel2a385e22015-01-09 16:47:20 +0000416 /// Keeps track of which block-value pairs are in BlockValueStack.
Hans Wennborg45172ac2014-11-25 17:23:05 +0000417 DenseSet<std::pair<BasicBlock*, Value*> > BlockValueSet;
418
Sanjay Patel2a385e22015-01-09 16:47:20 +0000419 /// Push BV onto BlockValueStack unless it's already in there.
420 /// Returns true on success.
Hans Wennborg45172ac2014-11-25 17:23:05 +0000421 bool pushBlockValue(const std::pair<BasicBlock *, Value *> &BV) {
Benjamin Kramer4e3b9032015-02-27 21:43:14 +0000422 if (!BlockValueSet.insert(BV).second)
Hans Wennborg45172ac2014-11-25 17:23:05 +0000423 return false; // It's already in the stack.
424
Philip Reames44456b82016-02-02 03:15:40 +0000425 DEBUG(dbgs() << "PUSH: " << *BV.second << " in " << BV.first->getName()
426 << "\n");
Hans Wennborg45172ac2014-11-25 17:23:05 +0000427 BlockValueStack.push(BV);
Hans Wennborg45172ac2014-11-25 17:23:05 +0000428 return true;
429 }
430
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000431 AssumptionCache *AC; ///< A pointer to the cache of @llvm.assume calls.
432 const DataLayout &DL; ///< A mandatory DataLayout
433 DominatorTree *DT; ///< An optional DT pointer.
434
Owen Anderson118ac802011-01-05 21:15:29 +0000435 friend struct LVIValueHandle;
Owen Anderson6f060af2011-01-05 23:26:22 +0000436
Hans Wennborg45172ac2014-11-25 17:23:05 +0000437 void insertResult(Value *Val, BasicBlock *BB, const LVILatticeVal &Result) {
438 SeenBlocks.insert(BB);
Akira Hatanaka2992bee2015-12-11 00:49:47 +0000439
440 // Insert over-defined values into their own cache to reduce memory
441 // overhead.
Hans Wennborg45172ac2014-11-25 17:23:05 +0000442 if (Result.isOverdefined())
Bruno Cardoso Lopes6ac4ea42015-08-18 16:34:27 +0000443 OverDefinedCache[BB].insert(Val);
Akira Hatanaka2992bee2015-12-11 00:49:47 +0000444 else
445 lookup(Val)[BB] = Result;
Hans Wennborg45172ac2014-11-25 17:23:05 +0000446 }
Owen Andersonc1561b82010-07-30 23:59:40 +0000447
Owen Andersonc7ed4dc2010-12-09 06:14:58 +0000448 LVILatticeVal getBlockValue(Value *Val, BasicBlock *BB);
Nick Lewycky55a700b2010-12-18 01:00:40 +0000449 bool getEdgeValue(Value *V, BasicBlock *F, BasicBlock *T,
Hal Finkel7e184492014-09-07 20:29:59 +0000450 LVILatticeVal &Result,
451 Instruction *CxtI = nullptr);
Nick Lewycky55a700b2010-12-18 01:00:40 +0000452 bool hasBlockValue(Value *Val, BasicBlock *BB);
453
454 // These methods process one work item and may add more. A false value
455 // returned means that the work item was not completely processed and must
456 // be revisited after going through the new items.
457 bool solveBlockValue(Value *Val, BasicBlock *BB);
Owen Anderson64c2c572010-12-20 18:18:16 +0000458 bool solveBlockValueNonLocal(LVILatticeVal &BBLV,
459 Value *Val, BasicBlock *BB);
460 bool solveBlockValuePHINode(LVILatticeVal &BBLV,
461 PHINode *PN, BasicBlock *BB);
Philip Reamesc0bdb0c2016-02-01 22:57:53 +0000462 bool solveBlockValueSelect(LVILatticeVal &BBLV,
Philip Reames66715772016-04-25 18:30:31 +0000463 SelectInst *S, BasicBlock *BB);
464 bool solveBlockValueBinaryOp(LVILatticeVal &BBLV,
465 Instruction *BBI, BasicBlock *BB);
466 bool solveBlockValueCast(LVILatticeVal &BBLV,
467 Instruction *BBI, BasicBlock *BB);
468 void intersectAssumeBlockValueConstantRange(Value *Val, LVILatticeVal &BBLV,
Hal Finkel7e184492014-09-07 20:29:59 +0000469 Instruction *BBI);
Nick Lewycky55a700b2010-12-18 01:00:40 +0000470
471 void solve();
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000472
Nick Lewycky11678bd2010-12-15 18:57:18 +0000473 ValueCacheEntryTy &lookup(Value *V) {
Owen Andersonc7ed4dc2010-12-09 06:14:58 +0000474 return ValueCache[LVIValueHandle(V, this)];
475 }
Nick Lewycky55a700b2010-12-18 01:00:40 +0000476
Akira Hatanaka2992bee2015-12-11 00:49:47 +0000477 bool isOverdefined(Value *V, BasicBlock *BB) const {
478 auto ODI = OverDefinedCache.find(BB);
479
480 if (ODI == OverDefinedCache.end())
481 return false;
482
483 return ODI->second.count(V);
484 }
485
486 bool hasCachedValueInfo(Value *V, BasicBlock *BB) {
487 if (isOverdefined(V, BB))
488 return true;
489
490 LVIValueHandle ValHandle(V, this);
491 auto I = ValueCache.find(ValHandle);
492 if (I == ValueCache.end())
493 return false;
494
495 return I->second.count(BB);
496 }
497
498 LVILatticeVal getCachedValueInfo(Value *V, BasicBlock *BB) {
499 if (isOverdefined(V, BB))
500 return LVILatticeVal::getOverdefined();
501
502 return lookup(V)[BB];
503 }
504
Chris Lattneraf025d32009-11-15 19:59:49 +0000505 public:
Sanjay Patel2a385e22015-01-09 16:47:20 +0000506 /// This is the query interface to determine the lattice
Chris Lattneraf025d32009-11-15 19:59:49 +0000507 /// value for the specified Value* at the end of the specified block.
Hal Finkel7e184492014-09-07 20:29:59 +0000508 LVILatticeVal getValueInBlock(Value *V, BasicBlock *BB,
509 Instruction *CxtI = nullptr);
510
Sanjay Patel2a385e22015-01-09 16:47:20 +0000511 /// This is the query interface to determine the lattice
Hal Finkel7e184492014-09-07 20:29:59 +0000512 /// value for the specified Value* at the specified instruction (generally
513 /// from an assume intrinsic).
514 LVILatticeVal getValueAt(Value *V, Instruction *CxtI);
Chris Lattneraf025d32009-11-15 19:59:49 +0000515
Sanjay Patel2a385e22015-01-09 16:47:20 +0000516 /// This is the query interface to determine the lattice
Chris Lattneraf025d32009-11-15 19:59:49 +0000517 /// value for the specified Value* that is true on the specified edge.
Hal Finkel7e184492014-09-07 20:29:59 +0000518 LVILatticeVal getValueOnEdge(Value *V, BasicBlock *FromBB,BasicBlock *ToBB,
519 Instruction *CxtI = nullptr);
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000520
Sanjay Patel2a385e22015-01-09 16:47:20 +0000521 /// This is the update interface to inform the cache that an edge from
522 /// PredBB to OldSucc has been threaded to be from PredBB to NewSucc.
Owen Andersonaa7f66b2010-07-26 18:48:03 +0000523 void threadEdge(BasicBlock *PredBB,BasicBlock *OldSucc,BasicBlock *NewSucc);
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000524
Sanjay Patel2a385e22015-01-09 16:47:20 +0000525 /// This is part of the update interface to inform the cache
Owen Anderson208636f2010-08-18 18:39:01 +0000526 /// that a block has been deleted.
527 void eraseBlock(BasicBlock *BB);
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000528
Owen Anderson208636f2010-08-18 18:39:01 +0000529 /// clear - Empty the cache.
530 void clear() {
Benjamin Kramerbbf3c602011-12-03 15:19:55 +0000531 SeenBlocks.clear();
Owen Anderson208636f2010-08-18 18:39:01 +0000532 ValueCache.clear();
533 OverDefinedCache.clear();
534 }
Hal Finkel7e184492014-09-07 20:29:59 +0000535
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000536 LazyValueInfoCache(AssumptionCache *AC, const DataLayout &DL,
Chandler Carruth66b31302015-01-04 12:03:27 +0000537 DominatorTree *DT = nullptr)
538 : AC(AC), DL(DL), DT(DT) {}
Chris Lattneraf025d32009-11-15 19:59:49 +0000539 };
540} // end anonymous namespace
541
Owen Anderson118ac802011-01-05 21:15:29 +0000542void LVIValueHandle::deleted() {
Bruno Cardoso Lopes6ac4ea42015-08-18 16:34:27 +0000543 SmallVector<AssertingVH<BasicBlock>, 4> ToErase;
544 for (auto &I : Parent->OverDefinedCache) {
545 SmallPtrSetImpl<Value *> &ValueSet = I.second;
546 if (ValueSet.count(getValPtr()))
547 ValueSet.erase(getValPtr());
548 if (ValueSet.empty())
549 ToErase.push_back(I.first);
550 }
551 for (auto &BB : ToErase)
552 Parent->OverDefinedCache.erase(BB);
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000553
Owen Anderson7b974a42010-08-11 22:36:04 +0000554 // This erasure deallocates *this, so it MUST happen after we're done
555 // using any and all members of *this.
556 Parent->ValueCache.erase(*this);
Owen Andersonc1561b82010-07-30 23:59:40 +0000557}
558
Owen Anderson208636f2010-08-18 18:39:01 +0000559void LazyValueInfoCache::eraseBlock(BasicBlock *BB) {
Benjamin Kramer36647082011-12-03 15:16:45 +0000560 // Shortcut if we have never seen this block.
561 DenseSet<AssertingVH<BasicBlock> >::iterator I = SeenBlocks.find(BB);
562 if (I == SeenBlocks.end())
563 return;
564 SeenBlocks.erase(I);
565
Bruno Cardoso Lopes6ac4ea42015-08-18 16:34:27 +0000566 auto ODI = OverDefinedCache.find(BB);
567 if (ODI != OverDefinedCache.end())
568 OverDefinedCache.erase(ODI);
Owen Anderson208636f2010-08-18 18:39:01 +0000569
Bruno Cardoso Lopes6ac4ea42015-08-18 16:34:27 +0000570 for (auto I = ValueCache.begin(), E = ValueCache.end(); I != E; ++I)
Owen Anderson208636f2010-08-18 18:39:01 +0000571 I->second.erase(BB);
572}
Owen Andersonc1561b82010-07-30 23:59:40 +0000573
Nick Lewycky55a700b2010-12-18 01:00:40 +0000574void LazyValueInfoCache::solve() {
Owen Anderson6f060af2011-01-05 23:26:22 +0000575 while (!BlockValueStack.empty()) {
576 std::pair<BasicBlock*, Value*> &e = BlockValueStack.top();
Hans Wennborg45172ac2014-11-25 17:23:05 +0000577 assert(BlockValueSet.count(e) && "Stack value should be in BlockValueSet!");
578
Nuno Lopese6e04902012-06-28 01:16:18 +0000579 if (solveBlockValue(e.second, e.first)) {
Hans Wennborg45172ac2014-11-25 17:23:05 +0000580 // The work item was completely processed.
581 assert(BlockValueStack.top() == e && "Nothing should have been pushed!");
Akira Hatanaka2992bee2015-12-11 00:49:47 +0000582 assert(hasCachedValueInfo(e.second, e.first) &&
583 "Result should be in cache!");
Hans Wennborg45172ac2014-11-25 17:23:05 +0000584
Philip Reames44456b82016-02-02 03:15:40 +0000585 DEBUG(dbgs() << "POP " << *e.second << " in " << e.first->getName()
Philip Reamesb7571042016-02-02 22:43:08 +0000586 << " = " << getCachedValueInfo(e.second, e.first) << "\n");
Philip Reames44456b82016-02-02 03:15:40 +0000587
Owen Anderson6f060af2011-01-05 23:26:22 +0000588 BlockValueStack.pop();
Hans Wennborg45172ac2014-11-25 17:23:05 +0000589 BlockValueSet.erase(e);
590 } else {
591 // More work needs to be done before revisiting.
592 assert(BlockValueStack.top() != e && "Stack should have been pushed!");
Nuno Lopese6e04902012-06-28 01:16:18 +0000593 }
Nick Lewycky55a700b2010-12-18 01:00:40 +0000594 }
595}
596
597bool LazyValueInfoCache::hasBlockValue(Value *Val, BasicBlock *BB) {
598 // If already a constant, there is nothing to compute.
599 if (isa<Constant>(Val))
600 return true;
601
Akira Hatanaka2992bee2015-12-11 00:49:47 +0000602 return hasCachedValueInfo(Val, BB);
Nick Lewycky55a700b2010-12-18 01:00:40 +0000603}
604
Owen Andersonc7ed4dc2010-12-09 06:14:58 +0000605LVILatticeVal LazyValueInfoCache::getBlockValue(Value *Val, BasicBlock *BB) {
Nick Lewycky55a700b2010-12-18 01:00:40 +0000606 // If already a constant, there is nothing to compute.
607 if (Constant *VC = dyn_cast<Constant>(Val))
608 return LVILatticeVal::get(VC);
609
Benjamin Kramer36647082011-12-03 15:16:45 +0000610 SeenBlocks.insert(BB);
Akira Hatanaka2992bee2015-12-11 00:49:47 +0000611 return getCachedValueInfo(Val, BB);
Nick Lewycky55a700b2010-12-18 01:00:40 +0000612}
613
Philip Reameseb3e9da2015-10-29 03:57:17 +0000614static LVILatticeVal getFromRangeMetadata(Instruction *BBI) {
615 switch (BBI->getOpcode()) {
616 default: break;
617 case Instruction::Load:
618 case Instruction::Call:
619 case Instruction::Invoke:
620 if (MDNode *Ranges = BBI->getMetadata(LLVMContext::MD_range))
Philip Reames70efccd2015-10-29 04:21:49 +0000621 if (isa<IntegerType>(BBI->getType())) {
Benjamin Kramer2337c1f2016-02-20 10:40:34 +0000622 return LVILatticeVal::getRange(getConstantRangeFromMetadata(*Ranges));
Philip Reameseb3e9da2015-10-29 03:57:17 +0000623 }
624 break;
625 };
Philip Reamesd1f829d2016-02-02 21:57:37 +0000626 // Nothing known - will be intersected with other facts
627 return LVILatticeVal::getOverdefined();
Philip Reameseb3e9da2015-10-29 03:57:17 +0000628}
629
Nick Lewycky55a700b2010-12-18 01:00:40 +0000630bool LazyValueInfoCache::solveBlockValue(Value *Val, BasicBlock *BB) {
631 if (isa<Constant>(Val))
632 return true;
633
Akira Hatanaka2992bee2015-12-11 00:49:47 +0000634 if (hasCachedValueInfo(Val, BB)) {
Hans Wennborg45172ac2014-11-25 17:23:05 +0000635 // If we have a cached value, use that.
636 DEBUG(dbgs() << " reuse BB '" << BB->getName()
Akira Hatanaka2992bee2015-12-11 00:49:47 +0000637 << "' val=" << getCachedValueInfo(Val, BB) << '\n');
Nick Lewycky55a700b2010-12-18 01:00:40 +0000638
Hans Wennborg45172ac2014-11-25 17:23:05 +0000639 // Since we're reusing a cached value, we don't need to update the
640 // OverDefinedCache. The cache will have been properly updated whenever the
641 // cached value was inserted.
Nick Lewycky55a700b2010-12-18 01:00:40 +0000642 return true;
Chris Lattner2c708562009-11-15 20:00:52 +0000643 }
644
Hans Wennborg45172ac2014-11-25 17:23:05 +0000645 // Hold off inserting this value into the Cache in case we have to return
646 // false and come back later.
647 LVILatticeVal Res;
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000648
Chris Lattneraf025d32009-11-15 19:59:49 +0000649 Instruction *BBI = dyn_cast<Instruction>(Val);
Craig Topper9f008862014-04-15 04:59:12 +0000650 if (!BBI || BBI->getParent() != BB) {
Hans Wennborg45172ac2014-11-25 17:23:05 +0000651 if (!solveBlockValueNonLocal(Res, Val, BB))
652 return false;
653 insertResult(Val, BB, Res);
654 return true;
Chris Lattneraf025d32009-11-15 19:59:49 +0000655 }
Chris Lattner2c708562009-11-15 20:00:52 +0000656
Nick Lewycky55a700b2010-12-18 01:00:40 +0000657 if (PHINode *PN = dyn_cast<PHINode>(BBI)) {
Hans Wennborg45172ac2014-11-25 17:23:05 +0000658 if (!solveBlockValuePHINode(Res, PN, BB))
659 return false;
660 insertResult(Val, BB, Res);
661 return true;
Nick Lewycky55a700b2010-12-18 01:00:40 +0000662 }
Owen Anderson80d19f02010-08-18 21:11:37 +0000663
Philip Reamesc0bdb0c2016-02-01 22:57:53 +0000664 if (auto *SI = dyn_cast<SelectInst>(BBI)) {
665 if (!solveBlockValueSelect(Res, SI, BB))
666 return false;
667 insertResult(Val, BB, Res);
668 return true;
669 }
670
Igor Laevsky0fa48192015-09-18 13:01:48 +0000671 // If this value is a nonnull pointer, record it's range and bailout.
672 PointerType *PT = dyn_cast<PointerType>(BBI->getType());
673 if (PT && isKnownNonNull(BBI)) {
674 Res = LVILatticeVal::getNot(ConstantPointerNull::get(PT));
Hans Wennborg45172ac2014-11-25 17:23:05 +0000675 insertResult(Val, BB, Res);
676 return true;
Nick Lewycky367f98f2011-01-15 09:16:12 +0000677 }
678
Philip Reamesa0c9f6e2016-03-04 22:27:39 +0000679 if (isa<CastInst>(BBI) && BBI->getType()->isIntegerTy()) {
Philip Reames66715772016-04-25 18:30:31 +0000680 if (!solveBlockValueCast(Res, BBI, BB))
Philip Reamesa0c9f6e2016-03-04 22:27:39 +0000681 return false;
Hans Wennborg45172ac2014-11-25 17:23:05 +0000682 insertResult(Val, BB, Res);
683 return true;
Owen Anderson80d19f02010-08-18 21:11:37 +0000684 }
Nick Lewycky55a700b2010-12-18 01:00:40 +0000685
Owen Anderson80d19f02010-08-18 21:11:37 +0000686 BinaryOperator *BO = dyn_cast<BinaryOperator>(BBI);
Philip Reamesa0c9f6e2016-03-04 22:27:39 +0000687 if (BO && isa<ConstantInt>(BO->getOperand(1))) {
Philip Reames66715772016-04-25 18:30:31 +0000688 if (!solveBlockValueBinaryOp(Res, BBI, BB))
Philip Reamesa0c9f6e2016-03-04 22:27:39 +0000689 return false;
Hans Wennborg45172ac2014-11-25 17:23:05 +0000690 insertResult(Val, BB, Res);
691 return true;
Nick Lewycky55a700b2010-12-18 01:00:40 +0000692 }
Owen Anderson80d19f02010-08-18 21:11:37 +0000693
Philip Reamesa0c9f6e2016-03-04 22:27:39 +0000694 DEBUG(dbgs() << " compute BB '" << BB->getName()
695 << "' - unknown inst def found.\n");
696 Res = getFromRangeMetadata(BBI);
Hans Wennborg45172ac2014-11-25 17:23:05 +0000697 insertResult(Val, BB, Res);
698 return true;
Nick Lewycky55a700b2010-12-18 01:00:40 +0000699}
700
701static bool InstructionDereferencesPointer(Instruction *I, Value *Ptr) {
702 if (LoadInst *L = dyn_cast<LoadInst>(I)) {
703 return L->getPointerAddressSpace() == 0 &&
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000704 GetUnderlyingObject(L->getPointerOperand(),
705 L->getModule()->getDataLayout()) == Ptr;
Nick Lewycky55a700b2010-12-18 01:00:40 +0000706 }
707 if (StoreInst *S = dyn_cast<StoreInst>(I)) {
708 return S->getPointerAddressSpace() == 0 &&
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000709 GetUnderlyingObject(S->getPointerOperand(),
710 S->getModule()->getDataLayout()) == Ptr;
Nick Lewycky55a700b2010-12-18 01:00:40 +0000711 }
Nick Lewycky367f98f2011-01-15 09:16:12 +0000712 if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I)) {
713 if (MI->isVolatile()) return false;
Nick Lewycky367f98f2011-01-15 09:16:12 +0000714
715 // FIXME: check whether it has a valuerange that excludes zero?
716 ConstantInt *Len = dyn_cast<ConstantInt>(MI->getLength());
717 if (!Len || Len->isZero()) return false;
718
Eli Friedman7a5fc692011-05-31 20:40:16 +0000719 if (MI->getDestAddressSpace() == 0)
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000720 if (GetUnderlyingObject(MI->getRawDest(),
721 MI->getModule()->getDataLayout()) == Ptr)
Eli Friedman7a5fc692011-05-31 20:40:16 +0000722 return true;
Nick Lewycky367f98f2011-01-15 09:16:12 +0000723 if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI))
Eli Friedman7a5fc692011-05-31 20:40:16 +0000724 if (MTI->getSourceAddressSpace() == 0)
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000725 if (GetUnderlyingObject(MTI->getRawSource(),
726 MTI->getModule()->getDataLayout()) == Ptr)
Eli Friedman7a5fc692011-05-31 20:40:16 +0000727 return true;
Nick Lewycky367f98f2011-01-15 09:16:12 +0000728 }
Nick Lewycky55a700b2010-12-18 01:00:40 +0000729 return false;
730}
731
Philip Reames3f83dbe2016-04-27 00:30:55 +0000732/// Return true if the allocation associated with Val is ever dereferenced
733/// within the given basic block. This establishes the fact Val is not null,
734/// but does not imply that the memory at Val is dereferenceable. (Val may
735/// point off the end of the dereferenceable part of the object.)
736static bool isObjectDereferencedInBlock(Value *Val, BasicBlock *BB) {
737 assert(Val->getType()->isPointerTy());
738
739 const DataLayout &DL = BB->getModule()->getDataLayout();
740 Value *UnderlyingVal = GetUnderlyingObject(Val, DL);
741 // If 'GetUnderlyingObject' didn't converge, skip it. It won't converge
742 // inside InstructionDereferencesPointer either.
743 if (UnderlyingVal == GetUnderlyingObject(UnderlyingVal, DL, 1))
744 for (Instruction &I : *BB)
745 if (InstructionDereferencesPointer(&I, UnderlyingVal))
746 return true;
747 return false;
748}
749
Owen Anderson64c2c572010-12-20 18:18:16 +0000750bool LazyValueInfoCache::solveBlockValueNonLocal(LVILatticeVal &BBLV,
751 Value *Val, BasicBlock *BB) {
Nick Lewycky55a700b2010-12-18 01:00:40 +0000752 LVILatticeVal Result; // Start Undefined.
753
Nick Lewycky55a700b2010-12-18 01:00:40 +0000754 // If this is the entry block, we must be asking about an argument. The
755 // value is overdefined.
756 if (BB == &BB->getParent()->getEntryBlock()) {
757 assert(isa<Argument>(Val) && "Unknown live-in to the entry block");
Philip Reames3f83dbe2016-04-27 00:30:55 +0000758 // Bofore giving up, see if we can prove the pointer non-null local to
759 // this particular block.
760 if (Val->getType()->isPointerTy() &&
761 (isKnownNonNull(Val) || isObjectDereferencedInBlock(Val, BB))) {
Chris Lattner229907c2011-07-18 04:54:35 +0000762 PointerType *PTy = cast<PointerType>(Val->getType());
Nick Lewycky55a700b2010-12-18 01:00:40 +0000763 Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy));
764 } else {
765 Result.markOverdefined();
766 }
Owen Anderson64c2c572010-12-20 18:18:16 +0000767 BBLV = Result;
Nick Lewycky55a700b2010-12-18 01:00:40 +0000768 return true;
769 }
770
771 // Loop over all of our predecessors, merging what we know from them into
772 // result.
773 bool EdgesMissing = false;
Duncan P. N. Exon Smith6c990152014-07-21 17:06:51 +0000774 for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
Nick Lewycky55a700b2010-12-18 01:00:40 +0000775 LVILatticeVal EdgeResult;
Duncan P. N. Exon Smith6c990152014-07-21 17:06:51 +0000776 EdgesMissing |= !getEdgeValue(Val, *PI, BB, EdgeResult);
Nick Lewycky55a700b2010-12-18 01:00:40 +0000777 if (EdgesMissing)
778 continue;
779
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000780 Result.mergeIn(EdgeResult, DL);
Nick Lewycky55a700b2010-12-18 01:00:40 +0000781
782 // If we hit overdefined, exit early. The BlockVals entry is already set
783 // to overdefined.
784 if (Result.isOverdefined()) {
785 DEBUG(dbgs() << " compute BB '" << BB->getName()
Philip Reamesb7571042016-02-02 22:43:08 +0000786 << "' - overdefined because of pred (non local).\n");
Philip Reames3f83dbe2016-04-27 00:30:55 +0000787 // Bofore giving up, see if we can prove the pointer non-null local to
788 // this particular block.
789 if (Val->getType()->isPointerTy() &&
790 isObjectDereferencedInBlock(Val, BB)) {
Chris Lattner229907c2011-07-18 04:54:35 +0000791 PointerType *PTy = cast<PointerType>(Val->getType());
Nick Lewycky55a700b2010-12-18 01:00:40 +0000792 Result = LVILatticeVal::getNot(ConstantPointerNull::get(PTy));
793 }
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000794
Owen Anderson64c2c572010-12-20 18:18:16 +0000795 BBLV = Result;
Nick Lewycky55a700b2010-12-18 01:00:40 +0000796 return true;
797 }
798 }
799 if (EdgesMissing)
800 return false;
801
802 // Return the merged value, which is more precise than 'overdefined'.
803 assert(!Result.isOverdefined());
Owen Anderson64c2c572010-12-20 18:18:16 +0000804 BBLV = Result;
Nick Lewycky55a700b2010-12-18 01:00:40 +0000805 return true;
806}
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000807
Owen Anderson64c2c572010-12-20 18:18:16 +0000808bool LazyValueInfoCache::solveBlockValuePHINode(LVILatticeVal &BBLV,
809 PHINode *PN, BasicBlock *BB) {
Nick Lewycky55a700b2010-12-18 01:00:40 +0000810 LVILatticeVal Result; // Start Undefined.
811
812 // Loop over all of our predecessors, merging what we know from them into
813 // result.
814 bool EdgesMissing = false;
815 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
816 BasicBlock *PhiBB = PN->getIncomingBlock(i);
817 Value *PhiVal = PN->getIncomingValue(i);
818 LVILatticeVal EdgeResult;
Hal Finkel2400c962014-10-16 00:40:05 +0000819 // Note that we can provide PN as the context value to getEdgeValue, even
820 // though the results will be cached, because PN is the value being used as
821 // the cache key in the caller.
Hal Finkel7e184492014-09-07 20:29:59 +0000822 EdgesMissing |= !getEdgeValue(PhiVal, PhiBB, BB, EdgeResult, PN);
Nick Lewycky55a700b2010-12-18 01:00:40 +0000823 if (EdgesMissing)
824 continue;
825
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000826 Result.mergeIn(EdgeResult, DL);
Nick Lewycky55a700b2010-12-18 01:00:40 +0000827
828 // If we hit overdefined, exit early. The BlockVals entry is already set
829 // to overdefined.
830 if (Result.isOverdefined()) {
831 DEBUG(dbgs() << " compute BB '" << BB->getName()
Philip Reamesb7571042016-02-02 22:43:08 +0000832 << "' - overdefined because of pred (local).\n");
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +0000833
Owen Anderson64c2c572010-12-20 18:18:16 +0000834 BBLV = Result;
Nick Lewycky55a700b2010-12-18 01:00:40 +0000835 return true;
836 }
837 }
838 if (EdgesMissing)
839 return false;
840
841 // Return the merged value, which is more precise than 'overdefined'.
842 assert(!Result.isOverdefined() && "Possible PHI in entry block?");
Owen Anderson64c2c572010-12-20 18:18:16 +0000843 BBLV = Result;
Nick Lewycky55a700b2010-12-18 01:00:40 +0000844 return true;
845}
846
Hal Finkel7e184492014-09-07 20:29:59 +0000847static bool getValueFromFromCondition(Value *Val, ICmpInst *ICI,
848 LVILatticeVal &Result,
849 bool isTrueDest = true);
850
Philip Reamesd1f829d2016-02-02 21:57:37 +0000851// If we can determine a constraint on the value given conditions assumed by
852// the program, intersect those constraints with BBLV
853void LazyValueInfoCache::intersectAssumeBlockValueConstantRange(Value *Val,
Hans Wennborgc5ec73d2014-11-21 18:58:23 +0000854 LVILatticeVal &BBLV,
855 Instruction *BBI) {
Hal Finkel7e184492014-09-07 20:29:59 +0000856 BBI = BBI ? BBI : dyn_cast<Instruction>(Val);
857 if (!BBI)
858 return;
859
Chandler Carruth66b31302015-01-04 12:03:27 +0000860 for (auto &AssumeVH : AC->assumptions()) {
861 if (!AssumeVH)
862 continue;
863 auto *I = cast<CallInst>(AssumeVH);
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000864 if (!isValidAssumeForContext(I, BBI, DT))
Hal Finkel7e184492014-09-07 20:29:59 +0000865 continue;
866
867 Value *C = I->getArgOperand(0);
868 if (ICmpInst *ICI = dyn_cast<ICmpInst>(C)) {
869 LVILatticeVal Result;
Philip Reamesd1f829d2016-02-02 21:57:37 +0000870 if (getValueFromFromCondition(Val, ICI, Result))
871 BBLV = intersect(BBLV, Result);
Hal Finkel7e184492014-09-07 20:29:59 +0000872 }
873 }
874}
875
Philip Reamesc0bdb0c2016-02-01 22:57:53 +0000876bool LazyValueInfoCache::solveBlockValueSelect(LVILatticeVal &BBLV,
877 SelectInst *SI, BasicBlock *BB) {
878
879 // Recurse on our inputs if needed
880 if (!hasBlockValue(SI->getTrueValue(), BB)) {
881 if (pushBlockValue(std::make_pair(BB, SI->getTrueValue())))
882 return false;
883 BBLV.markOverdefined();
884 return true;
885 }
886 LVILatticeVal TrueVal = getBlockValue(SI->getTrueValue(), BB);
887 // If we hit overdefined, don't ask more queries. We want to avoid poisoning
888 // extra slots in the table if we can.
889 if (TrueVal.isOverdefined()) {
890 BBLV.markOverdefined();
891 return true;
892 }
893
894 if (!hasBlockValue(SI->getFalseValue(), BB)) {
895 if (pushBlockValue(std::make_pair(BB, SI->getFalseValue())))
896 return false;
897 BBLV.markOverdefined();
898 return true;
899 }
900 LVILatticeVal FalseVal = getBlockValue(SI->getFalseValue(), BB);
901 // If we hit overdefined, don't ask more queries. We want to avoid poisoning
902 // extra slots in the table if we can.
903 if (FalseVal.isOverdefined()) {
904 BBLV.markOverdefined();
905 return true;
906 }
907
Philip Reamesadf0e352016-02-26 22:53:59 +0000908 if (TrueVal.isConstantRange() && FalseVal.isConstantRange()) {
909 ConstantRange TrueCR = TrueVal.getConstantRange();
910 ConstantRange FalseCR = FalseVal.getConstantRange();
911 Value *LHS = nullptr;
912 Value *RHS = nullptr;
913 SelectPatternResult SPR = matchSelectPattern(SI, LHS, RHS);
914 // Is this a min specifically of our two inputs? (Avoid the risk of
915 // ValueTracking getting smarter looking back past our immediate inputs.)
916 if (SelectPatternResult::isMinOrMax(SPR.Flavor) &&
917 LHS == SI->getTrueValue() && RHS == SI->getFalseValue()) {
918 switch (SPR.Flavor) {
919 default:
920 llvm_unreachable("unexpected minmax type!");
921 case SPF_SMIN: /// Signed minimum
922 BBLV.markConstantRange(TrueCR.smin(FalseCR));
923 return true;
924 case SPF_UMIN: /// Unsigned minimum
925 BBLV.markConstantRange(TrueCR.umin(FalseCR));
926 return true;
927 case SPF_SMAX: /// Signed maximum
928 BBLV.markConstantRange(TrueCR.smax(FalseCR));
929 return true;
930 case SPF_UMAX: /// Unsigned maximum
931 BBLV.markConstantRange(TrueCR.umax(FalseCR));
932 return true;
933 };
934 }
935
936 // TODO: ABS, NABS from the SelectPatternResult
937 }
938
Philip Reames854a84c2016-02-12 00:09:18 +0000939 // Can we constrain the facts about the true and false values by using the
940 // condition itself? This shows up with idioms like e.g. select(a > 5, a, 5).
941 // TODO: We could potentially refine an overdefined true value above.
942 if (auto *ICI = dyn_cast<ICmpInst>(SI->getCondition())) {
943 LVILatticeVal TrueValTaken, FalseValTaken;
944 if (!getValueFromFromCondition(SI->getTrueValue(), ICI,
945 TrueValTaken, true))
946 TrueValTaken.markOverdefined();
947 if (!getValueFromFromCondition(SI->getFalseValue(), ICI,
948 FalseValTaken, false))
949 FalseValTaken.markOverdefined();
950
951 TrueVal = intersect(TrueVal, TrueValTaken);
952 FalseVal = intersect(FalseVal, FalseValTaken);
Philip Reames854a84c2016-02-12 00:09:18 +0000953
Philip Reamesadf0e352016-02-26 22:53:59 +0000954
955 // Handle clamp idioms such as:
956 // %24 = constantrange<0, 17>
957 // %39 = icmp eq i32 %24, 0
958 // %40 = add i32 %24, -1
959 // %siv.next = select i1 %39, i32 16, i32 %40
960 // %siv.next = constantrange<0, 17> not <-1, 17>
961 // In general, this can handle any clamp idiom which tests the edge
962 // condition via an equality or inequality.
963 ICmpInst::Predicate Pred = ICI->getPredicate();
964 Value *A = ICI->getOperand(0);
965 if (ConstantInt *CIBase = dyn_cast<ConstantInt>(ICI->getOperand(1))) {
966 auto addConstants = [](ConstantInt *A, ConstantInt *B) {
967 assert(A->getType() == B->getType());
968 return ConstantInt::get(A->getType(), A->getValue() + B->getValue());
969 };
970 // See if either input is A + C2, subject to the constraint from the
971 // condition that A != C when that input is used. We can assume that
972 // that input doesn't include C + C2.
973 ConstantInt *CIAdded;
974 switch (Pred) {
Philip Reames70b39182016-02-27 05:18:30 +0000975 default: break;
Philip Reamesadf0e352016-02-26 22:53:59 +0000976 case ICmpInst::ICMP_EQ:
977 if (match(SI->getFalseValue(), m_Add(m_Specific(A),
978 m_ConstantInt(CIAdded)))) {
979 auto ResNot = addConstants(CIBase, CIAdded);
980 FalseVal = intersect(FalseVal,
981 LVILatticeVal::getNot(ResNot));
982 }
983 break;
984 case ICmpInst::ICMP_NE:
985 if (match(SI->getTrueValue(), m_Add(m_Specific(A),
986 m_ConstantInt(CIAdded)))) {
987 auto ResNot = addConstants(CIBase, CIAdded);
988 TrueVal = intersect(TrueVal,
989 LVILatticeVal::getNot(ResNot));
990 }
991 break;
992 };
993 }
994 }
Philip Reames854a84c2016-02-12 00:09:18 +0000995
Philip Reamesc0bdb0c2016-02-01 22:57:53 +0000996 LVILatticeVal Result; // Start Undefined.
997 Result.mergeIn(TrueVal, DL);
998 Result.mergeIn(FalseVal, DL);
Philip Reamesc0bdb0c2016-02-01 22:57:53 +0000999 BBLV = Result;
1000 return true;
1001}
1002
Philip Reames66715772016-04-25 18:30:31 +00001003bool LazyValueInfoCache::solveBlockValueCast(LVILatticeVal &BBLV,
1004 Instruction *BBI,
Philip Reamese5030e82016-04-26 22:52:30 +00001005 BasicBlock *BB) {
1006 if (!BBI->getOperand(0)->getType()->isSized()) {
1007 // Without knowing how wide the input is, we can't analyze it in any useful
1008 // way.
1009 BBLV.markOverdefined();
1010 return true;
1011 }
Philip Reamesf105db42016-04-26 23:27:33 +00001012
1013 // Filter out casts we don't know how to reason about before attempting to
1014 // recurse on our operand. This can cut a long search short if we know we're
1015 // not going to be able to get any useful information anways.
1016 switch (BBI->getOpcode()) {
1017 case Instruction::Trunc:
1018 case Instruction::SExt:
1019 case Instruction::ZExt:
1020 case Instruction::BitCast:
1021 break;
1022 default:
1023 // Unhandled instructions are overdefined.
1024 DEBUG(dbgs() << " compute BB '" << BB->getName()
1025 << "' - overdefined (unknown cast).\n");
1026 BBLV.markOverdefined();
1027 return true;
1028 }
1029
Philip Reamese5030e82016-04-26 22:52:30 +00001030
Philip Reames38c87c22016-04-26 21:48:16 +00001031 // Figure out the range of the LHS. If that fails, we still apply the
1032 // transfer rule on the full set since we may be able to locally infer
1033 // interesting facts.
1034 if (!hasBlockValue(BBI->getOperand(0), BB))
Hans Wennborg45172ac2014-11-25 17:23:05 +00001035 if (pushBlockValue(std::make_pair(BB, BBI->getOperand(0))))
Philip Reames38c87c22016-04-26 21:48:16 +00001036 // More work to do before applying this transfer rule.
Hans Wennborg45172ac2014-11-25 17:23:05 +00001037 return false;
Philip Reames38c87c22016-04-26 21:48:16 +00001038
1039 const unsigned OperandBitWidth =
Philip Reamese5030e82016-04-26 22:52:30 +00001040 DL.getTypeSizeInBits(BBI->getOperand(0)->getType());
Philip Reames38c87c22016-04-26 21:48:16 +00001041 ConstantRange LHSRange = ConstantRange(OperandBitWidth);
1042 if (hasBlockValue(BBI->getOperand(0), BB)) {
1043 LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB);
1044 intersectAssumeBlockValueConstantRange(BBI->getOperand(0), LHSVal, BBI);
1045 if (LHSVal.isConstantRange())
1046 LHSRange = LHSVal.getConstantRange();
Nick Lewycky55a700b2010-12-18 01:00:40 +00001047 }
1048
Philip Reames38c87c22016-04-26 21:48:16 +00001049 const unsigned ResultBitWidth =
1050 cast<IntegerType>(BBI->getType())->getBitWidth();
Philip Reames66715772016-04-25 18:30:31 +00001051
1052 // NOTE: We're currently limited by the set of operations that ConstantRange
1053 // can evaluate symbolically. Enhancing that set will allows us to analyze
1054 // more definitions.
1055 LVILatticeVal Result;
1056 switch (BBI->getOpcode()) {
1057 case Instruction::Trunc:
Philip Reames38c87c22016-04-26 21:48:16 +00001058 Result.markConstantRange(LHSRange.truncate(ResultBitWidth));
Philip Reames66715772016-04-25 18:30:31 +00001059 break;
1060 case Instruction::SExt:
Philip Reames38c87c22016-04-26 21:48:16 +00001061 Result.markConstantRange(LHSRange.signExtend(ResultBitWidth));
Philip Reames66715772016-04-25 18:30:31 +00001062 break;
1063 case Instruction::ZExt:
Philip Reames38c87c22016-04-26 21:48:16 +00001064 Result.markConstantRange(LHSRange.zeroExtend(ResultBitWidth));
Philip Reames66715772016-04-25 18:30:31 +00001065 break;
1066 case Instruction::BitCast:
1067 Result.markConstantRange(LHSRange);
1068 break;
Philip Reames66715772016-04-25 18:30:31 +00001069 default:
Philip Reamesf105db42016-04-26 23:27:33 +00001070 // Should be dead if the code above is correct
1071 llvm_unreachable("inconsistent with above");
Philip Reames66715772016-04-25 18:30:31 +00001072 break;
Owen Anderson80d19f02010-08-18 21:11:37 +00001073 }
Nick Lewycky55a700b2010-12-18 01:00:40 +00001074
Philip Reames66715772016-04-25 18:30:31 +00001075 BBLV = Result;
1076 return true;
1077}
1078
1079bool LazyValueInfoCache::solveBlockValueBinaryOp(LVILatticeVal &BBLV,
1080 Instruction *BBI,
Philip Reamese5030e82016-04-26 22:52:30 +00001081 BasicBlock *BB) {
Philip Reames66715772016-04-25 18:30:31 +00001082
Philip Reames053c2a62016-04-26 23:10:35 +00001083 assert(BBI->getOperand(0)->getType()->isSized() &&
1084 "all operands to binary operators are sized");
Philip Reamesf105db42016-04-26 23:27:33 +00001085
1086 // Filter out operators we don't know how to reason about before attempting to
1087 // recurse on our operand(s). This can cut a long search short if we know
1088 // we're not going to be able to get any useful information anways.
1089 switch (BBI->getOpcode()) {
1090 case Instruction::Add:
1091 case Instruction::Sub:
1092 case Instruction::Mul:
1093 case Instruction::UDiv:
1094 case Instruction::Shl:
1095 case Instruction::LShr:
1096 case Instruction::And:
1097 case Instruction::Or:
1098 // continue into the code below
1099 break;
1100 default:
1101 // Unhandled instructions are overdefined.
1102 DEBUG(dbgs() << " compute BB '" << BB->getName()
1103 << "' - overdefined (unknown binary operator).\n");
1104 BBLV.markOverdefined();
1105 return true;
1106 };
Philip Reames053c2a62016-04-26 23:10:35 +00001107
1108 // Figure out the range of the LHS. If that fails, use a conservative range,
1109 // but apply the transfer rule anyways. This lets us pick up facts from
1110 // expressions like "and i32 (call i32 @foo()), 32"
1111 if (!hasBlockValue(BBI->getOperand(0), BB))
1112 if (pushBlockValue(std::make_pair(BB, BBI->getOperand(0))))
1113 // More work to do before applying this transfer rule.
1114 return false;
1115
1116 const unsigned OperandBitWidth =
1117 DL.getTypeSizeInBits(BBI->getOperand(0)->getType());
1118 ConstantRange LHSRange = ConstantRange(OperandBitWidth);
1119 if (hasBlockValue(BBI->getOperand(0), BB)) {
1120 LVILatticeVal LHSVal = getBlockValue(BBI->getOperand(0), BB);
1121 intersectAssumeBlockValueConstantRange(BBI->getOperand(0), LHSVal, BBI);
1122 if (LHSVal.isConstantRange())
1123 LHSRange = LHSVal.getConstantRange();
Philip Reames66715772016-04-25 18:30:31 +00001124 }
Philip Reames66715772016-04-25 18:30:31 +00001125
1126 ConstantInt *RHS = cast<ConstantInt>(BBI->getOperand(1));
1127 ConstantRange RHSRange = ConstantRange(RHS->getValue());
1128
Owen Anderson80d19f02010-08-18 21:11:37 +00001129 // NOTE: We're currently limited by the set of operations that ConstantRange
1130 // can evaluate symbolically. Enhancing that set will allows us to analyze
1131 // more definitions.
Owen Anderson64c2c572010-12-20 18:18:16 +00001132 LVILatticeVal Result;
Owen Anderson80d19f02010-08-18 21:11:37 +00001133 switch (BBI->getOpcode()) {
1134 case Instruction::Add:
1135 Result.markConstantRange(LHSRange.add(RHSRange));
1136 break;
1137 case Instruction::Sub:
1138 Result.markConstantRange(LHSRange.sub(RHSRange));
1139 break;
1140 case Instruction::Mul:
1141 Result.markConstantRange(LHSRange.multiply(RHSRange));
1142 break;
1143 case Instruction::UDiv:
1144 Result.markConstantRange(LHSRange.udiv(RHSRange));
1145 break;
1146 case Instruction::Shl:
1147 Result.markConstantRange(LHSRange.shl(RHSRange));
1148 break;
1149 case Instruction::LShr:
1150 Result.markConstantRange(LHSRange.lshr(RHSRange));
1151 break;
Nick Lewyckyad48e012010-09-07 05:39:02 +00001152 case Instruction::And:
1153 Result.markConstantRange(LHSRange.binaryAnd(RHSRange));
1154 break;
1155 case Instruction::Or:
1156 Result.markConstantRange(LHSRange.binaryOr(RHSRange));
1157 break;
Owen Anderson80d19f02010-08-18 21:11:37 +00001158 default:
Philip Reamesf105db42016-04-26 23:27:33 +00001159 // Should be dead if the code above is correct
1160 llvm_unreachable("inconsistent with above");
Owen Anderson80d19f02010-08-18 21:11:37 +00001161 break;
1162 }
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001163
Owen Anderson64c2c572010-12-20 18:18:16 +00001164 BBLV = Result;
Nick Lewycky55a700b2010-12-18 01:00:40 +00001165 return true;
Chris Lattner741c94c2009-11-11 00:22:30 +00001166}
1167
Hal Finkel7e184492014-09-07 20:29:59 +00001168bool getValueFromFromCondition(Value *Val, ICmpInst *ICI,
1169 LVILatticeVal &Result, bool isTrueDest) {
Philip Reames19183842016-04-25 22:21:24 +00001170 assert(ICI && "precondition");
1171 if (isa<Constant>(ICI->getOperand(1))) {
Hal Finkel7e184492014-09-07 20:29:59 +00001172 if (ICI->isEquality() && ICI->getOperand(0) == Val) {
1173 // We know that V has the RHS constant if this is a true SETEQ or
1174 // false SETNE.
1175 if (isTrueDest == (ICI->getPredicate() == ICmpInst::ICMP_EQ))
1176 Result = LVILatticeVal::get(cast<Constant>(ICI->getOperand(1)));
1177 else
1178 Result = LVILatticeVal::getNot(cast<Constant>(ICI->getOperand(1)));
1179 return true;
1180 }
1181
1182 // Recognize the range checking idiom that InstCombine produces.
1183 // (X-C1) u< C2 --> [C1, C1+C2)
1184 ConstantInt *NegOffset = nullptr;
1185 if (ICI->getPredicate() == ICmpInst::ICMP_ULT)
1186 match(ICI->getOperand(0), m_Add(m_Specific(Val),
1187 m_ConstantInt(NegOffset)));
1188
1189 ConstantInt *CI = dyn_cast<ConstantInt>(ICI->getOperand(1));
1190 if (CI && (ICI->getOperand(0) == Val || NegOffset)) {
Sanjoy Das7182d362015-03-18 00:41:24 +00001191 // Calculate the range of values that are allowed by the comparison
Hal Finkel7e184492014-09-07 20:29:59 +00001192 ConstantRange CmpRange(CI->getValue());
1193 ConstantRange TrueValues =
Sanjoy Das7182d362015-03-18 00:41:24 +00001194 ConstantRange::makeAllowedICmpRegion(ICI->getPredicate(), CmpRange);
Hal Finkel7e184492014-09-07 20:29:59 +00001195
1196 if (NegOffset) // Apply the offset from above.
1197 TrueValues = TrueValues.subtract(NegOffset->getValue());
1198
1199 // If we're interested in the false dest, invert the condition.
1200 if (!isTrueDest) TrueValues = TrueValues.inverse();
1201
Benjamin Kramer2337c1f2016-02-20 10:40:34 +00001202 Result = LVILatticeVal::getRange(std::move(TrueValues));
Hal Finkel7e184492014-09-07 20:29:59 +00001203 return true;
1204 }
1205 }
Philip Reames38c87c22016-04-26 21:48:16 +00001206
Hal Finkel7e184492014-09-07 20:29:59 +00001207 return false;
1208}
1209
Nuno Lopese6e04902012-06-28 01:16:18 +00001210/// \brief Compute the value of Val on the edge BBFrom -> BBTo. Returns false if
Philip Reames13f73242016-02-01 23:21:11 +00001211/// Val is not constrained on the edge. Result is unspecified if return value
1212/// is false.
Nuno Lopese6e04902012-06-28 01:16:18 +00001213static bool getEdgeValueLocal(Value *Val, BasicBlock *BBFrom,
1214 BasicBlock *BBTo, LVILatticeVal &Result) {
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001215 // TODO: Handle more complex conditionals. If (v == 0 || v2 < 1) is false, we
Chris Lattner77358782009-11-15 20:02:12 +00001216 // know that v != 0.
Chris Lattner19019ea2009-11-11 22:48:44 +00001217 if (BranchInst *BI = dyn_cast<BranchInst>(BBFrom->getTerminator())) {
1218 // If this is a conditional branch and only one successor goes to BBTo, then
Sanjay Patel938e2792015-01-09 16:35:37 +00001219 // we may be able to infer something from the condition.
Chris Lattner19019ea2009-11-11 22:48:44 +00001220 if (BI->isConditional() &&
1221 BI->getSuccessor(0) != BI->getSuccessor(1)) {
1222 bool isTrueDest = BI->getSuccessor(0) == BBTo;
1223 assert(BI->getSuccessor(!isTrueDest) == BBTo &&
1224 "BBTo isn't a successor of BBFrom");
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001225
Chris Lattner19019ea2009-11-11 22:48:44 +00001226 // If V is the condition of the branch itself, then we know exactly what
1227 // it is.
Nick Lewycky55a700b2010-12-18 01:00:40 +00001228 if (BI->getCondition() == Val) {
1229 Result = LVILatticeVal::get(ConstantInt::get(
Owen Anderson185fe002010-08-10 20:03:09 +00001230 Type::getInt1Ty(Val->getContext()), isTrueDest));
Nick Lewycky55a700b2010-12-18 01:00:40 +00001231 return true;
1232 }
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001233
Chris Lattner19019ea2009-11-11 22:48:44 +00001234 // If the condition of the branch is an equality comparison, we may be
1235 // able to infer the value.
Sanjay Pateld7291152015-01-09 16:28:15 +00001236 if (ICmpInst *ICI = dyn_cast<ICmpInst>(BI->getCondition()))
1237 if (getValueFromFromCondition(Val, ICI, Result, isTrueDest))
1238 return true;
Chris Lattner19019ea2009-11-11 22:48:44 +00001239 }
1240 }
Chris Lattner77358782009-11-15 20:02:12 +00001241
1242 // If the edge was formed by a switch on the value, then we may know exactly
1243 // what it is.
1244 if (SwitchInst *SI = dyn_cast<SwitchInst>(BBFrom->getTerminator())) {
Nuno Lopes8650fb82012-06-28 16:13:37 +00001245 if (SI->getCondition() != Val)
1246 return false;
1247
1248 bool DefaultCase = SI->getDefaultDest() == BBTo;
1249 unsigned BitWidth = Val->getType()->getIntegerBitWidth();
1250 ConstantRange EdgesVals(BitWidth, DefaultCase/*isFullSet*/);
1251
Hans Wennborgcbb18e32014-11-21 19:07:46 +00001252 for (SwitchInst::CaseIt i : SI->cases()) {
Nuno Lopes8650fb82012-06-28 16:13:37 +00001253 ConstantRange EdgeVal(i.getCaseValue()->getValue());
Manman Renf3fedb62012-09-05 23:45:58 +00001254 if (DefaultCase) {
1255 // It is possible that the default destination is the destination of
1256 // some cases. There is no need to perform difference for those cases.
1257 if (i.getCaseSuccessor() != BBTo)
1258 EdgesVals = EdgesVals.difference(EdgeVal);
1259 } else if (i.getCaseSuccessor() == BBTo)
Nuno Lopesac593802012-05-18 21:02:10 +00001260 EdgesVals = EdgesVals.unionWith(EdgeVal);
Chris Lattner77358782009-11-15 20:02:12 +00001261 }
Benjamin Kramer2337c1f2016-02-20 10:40:34 +00001262 Result = LVILatticeVal::getRange(std::move(EdgesVals));
Nuno Lopes8650fb82012-06-28 16:13:37 +00001263 return true;
Chris Lattner77358782009-11-15 20:02:12 +00001264 }
Nuno Lopese6e04902012-06-28 01:16:18 +00001265 return false;
1266}
1267
Sanjay Patel938e2792015-01-09 16:35:37 +00001268/// \brief Compute the value of Val on the edge BBFrom -> BBTo or the value at
1269/// the basic block if the edge does not constrain Val.
Nuno Lopese6e04902012-06-28 01:16:18 +00001270bool LazyValueInfoCache::getEdgeValue(Value *Val, BasicBlock *BBFrom,
Hal Finkel7e184492014-09-07 20:29:59 +00001271 BasicBlock *BBTo, LVILatticeVal &Result,
1272 Instruction *CxtI) {
Nuno Lopese6e04902012-06-28 01:16:18 +00001273 // If already a constant, there is nothing to compute.
1274 if (Constant *VC = dyn_cast<Constant>(Val)) {
1275 Result = LVILatticeVal::get(VC);
Nick Lewycky55a700b2010-12-18 01:00:40 +00001276 return true;
1277 }
Nuno Lopese6e04902012-06-28 01:16:18 +00001278
Philip Reames44456b82016-02-02 03:15:40 +00001279 LVILatticeVal LocalResult;
1280 if (!getEdgeValueLocal(Val, BBFrom, BBTo, LocalResult))
1281 // If we couldn't constrain the value on the edge, LocalResult doesn't
1282 // provide any information.
1283 LocalResult.markOverdefined();
1284
1285 if (hasSingleValue(LocalResult)) {
1286 // Can't get any more precise here
1287 Result = LocalResult;
Nuno Lopese6e04902012-06-28 01:16:18 +00001288 return true;
1289 }
1290
1291 if (!hasBlockValue(Val, BBFrom)) {
Hans Wennborg45172ac2014-11-25 17:23:05 +00001292 if (pushBlockValue(std::make_pair(BBFrom, Val)))
1293 return false;
Philip Reames44456b82016-02-02 03:15:40 +00001294 // No new information.
1295 Result = LocalResult;
Hans Wennborg45172ac2014-11-25 17:23:05 +00001296 return true;
Nuno Lopese6e04902012-06-28 01:16:18 +00001297 }
1298
Philip Reames44456b82016-02-02 03:15:40 +00001299 // Try to intersect ranges of the BB and the constraint on the edge.
1300 LVILatticeVal InBlock = getBlockValue(Val, BBFrom);
Philip Reamesd1f829d2016-02-02 21:57:37 +00001301 intersectAssumeBlockValueConstantRange(Val, InBlock, BBFrom->getTerminator());
Hal Finkel2400c962014-10-16 00:40:05 +00001302 // We can use the context instruction (generically the ultimate instruction
1303 // the calling pass is trying to simplify) here, even though the result of
1304 // this function is generally cached when called from the solve* functions
1305 // (and that cached result might be used with queries using a different
1306 // context instruction), because when this function is called from the solve*
1307 // functions, the context instruction is not provided. When called from
1308 // LazyValueInfoCache::getValueOnEdge, the context instruction is provided,
1309 // but then the result is not cached.
Philip Reamesd1f829d2016-02-02 21:57:37 +00001310 intersectAssumeBlockValueConstantRange(Val, InBlock, CxtI);
Philip Reames44456b82016-02-02 03:15:40 +00001311
1312 Result = intersect(LocalResult, InBlock);
Nuno Lopese6e04902012-06-28 01:16:18 +00001313 return true;
Chris Lattner19019ea2009-11-11 22:48:44 +00001314}
1315
Hal Finkel7e184492014-09-07 20:29:59 +00001316LVILatticeVal LazyValueInfoCache::getValueInBlock(Value *V, BasicBlock *BB,
1317 Instruction *CxtI) {
David Greene37e98092009-12-23 20:43:58 +00001318 DEBUG(dbgs() << "LVI Getting block end value " << *V << " at '"
Chris Lattneraf025d32009-11-15 19:59:49 +00001319 << BB->getName() << "'\n");
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001320
Hans Wennborg45172ac2014-11-25 17:23:05 +00001321 assert(BlockValueStack.empty() && BlockValueSet.empty());
Philip Reamesbb781b42016-02-10 21:46:32 +00001322 if (!hasBlockValue(V, BB)) {
1323 pushBlockValue(std::make_pair(BB, V));
1324 solve();
1325 }
Owen Andersonc7ed4dc2010-12-09 06:14:58 +00001326 LVILatticeVal Result = getBlockValue(V, BB);
Philip Reamesd1f829d2016-02-02 21:57:37 +00001327 intersectAssumeBlockValueConstantRange(V, Result, CxtI);
Hal Finkel7e184492014-09-07 20:29:59 +00001328
1329 DEBUG(dbgs() << " Result = " << Result << "\n");
1330 return Result;
1331}
1332
1333LVILatticeVal LazyValueInfoCache::getValueAt(Value *V, Instruction *CxtI) {
1334 DEBUG(dbgs() << "LVI Getting value " << *V << " at '"
1335 << CxtI->getName() << "'\n");
1336
Philip Reamesbb781b42016-02-10 21:46:32 +00001337 if (auto *C = dyn_cast<Constant>(V))
1338 return LVILatticeVal::get(C);
1339
Philip Reamesd1f829d2016-02-02 21:57:37 +00001340 LVILatticeVal Result = LVILatticeVal::getOverdefined();
Philip Reameseb3e9da2015-10-29 03:57:17 +00001341 if (auto *I = dyn_cast<Instruction>(V))
1342 Result = getFromRangeMetadata(I);
Philip Reamesd1f829d2016-02-02 21:57:37 +00001343 intersectAssumeBlockValueConstantRange(V, Result, CxtI);
Philip Reames2c275cc2016-02-02 00:45:30 +00001344
David Greene37e98092009-12-23 20:43:58 +00001345 DEBUG(dbgs() << " Result = " << Result << "\n");
Chris Lattneraf025d32009-11-15 19:59:49 +00001346 return Result;
1347}
Chris Lattner19019ea2009-11-11 22:48:44 +00001348
Chris Lattneraf025d32009-11-15 19:59:49 +00001349LVILatticeVal LazyValueInfoCache::
Hal Finkel7e184492014-09-07 20:29:59 +00001350getValueOnEdge(Value *V, BasicBlock *FromBB, BasicBlock *ToBB,
1351 Instruction *CxtI) {
David Greene37e98092009-12-23 20:43:58 +00001352 DEBUG(dbgs() << "LVI Getting edge value " << *V << " from '"
Chris Lattneraf025d32009-11-15 19:59:49 +00001353 << FromBB->getName() << "' to '" << ToBB->getName() << "'\n");
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001354
Nick Lewycky55a700b2010-12-18 01:00:40 +00001355 LVILatticeVal Result;
Hal Finkel7e184492014-09-07 20:29:59 +00001356 if (!getEdgeValue(V, FromBB, ToBB, Result, CxtI)) {
Nick Lewycky55a700b2010-12-18 01:00:40 +00001357 solve();
Hal Finkel7e184492014-09-07 20:29:59 +00001358 bool WasFastQuery = getEdgeValue(V, FromBB, ToBB, Result, CxtI);
Nick Lewycky55a700b2010-12-18 01:00:40 +00001359 (void)WasFastQuery;
1360 assert(WasFastQuery && "More work to do after problem solved?");
1361 }
1362
David Greene37e98092009-12-23 20:43:58 +00001363 DEBUG(dbgs() << " Result = " << Result << "\n");
Chris Lattneraf025d32009-11-15 19:59:49 +00001364 return Result;
1365}
1366
Owen Andersonaa7f66b2010-07-26 18:48:03 +00001367void LazyValueInfoCache::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
1368 BasicBlock *NewSucc) {
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001369 // When an edge in the graph has been threaded, values that we could not
1370 // determine a value for before (i.e. were marked overdefined) may be
1371 // possible to solve now. We do NOT try to proactively update these values.
1372 // Instead, we clear their entries from the cache, and allow lazy updating to
1373 // recompute them when needed.
1374
Hans Wennborgc5ec73d2014-11-21 18:58:23 +00001375 // The updating process is fairly simple: we need to drop cached info
Owen Andersonaa7f66b2010-07-26 18:48:03 +00001376 // for all values that were marked overdefined in OldSucc, and for those same
1377 // values in any successor of OldSucc (except NewSucc) in which they were
1378 // also marked overdefined.
1379 std::vector<BasicBlock*> worklist;
1380 worklist.push_back(OldSucc);
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001381
Bruno Cardoso Lopes6ac4ea42015-08-18 16:34:27 +00001382 auto I = OverDefinedCache.find(OldSucc);
1383 if (I == OverDefinedCache.end())
1384 return; // Nothing to process here.
Bruno Cardoso Lopes7a1483e2015-08-21 21:18:26 +00001385 SmallVector<Value *, 4> ValsToClear(I->second.begin(), I->second.end());
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001386
Owen Andersonaa7f66b2010-07-26 18:48:03 +00001387 // Use a worklist to perform a depth-first search of OldSucc's successors.
1388 // NOTE: We do not need a visited list since any blocks we have already
1389 // visited will have had their overdefined markers cleared already, and we
1390 // thus won't loop to their successors.
1391 while (!worklist.empty()) {
1392 BasicBlock *ToUpdate = worklist.back();
1393 worklist.pop_back();
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001394
Owen Andersonaa7f66b2010-07-26 18:48:03 +00001395 // Skip blocks only accessible through NewSucc.
1396 if (ToUpdate == NewSucc) continue;
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001397
Owen Andersonaa7f66b2010-07-26 18:48:03 +00001398 bool changed = false;
Bruno Cardoso Lopes7a1483e2015-08-21 21:18:26 +00001399 for (Value *V : ValsToClear) {
Owen Andersonaa7f66b2010-07-26 18:48:03 +00001400 // If a value was marked overdefined in OldSucc, and is here too...
Bruno Cardoso Lopes6ac4ea42015-08-18 16:34:27 +00001401 auto OI = OverDefinedCache.find(ToUpdate);
1402 if (OI == OverDefinedCache.end())
1403 continue;
1404 SmallPtrSetImpl<Value *> &ValueSet = OI->second;
1405 if (!ValueSet.count(V))
1406 continue;
Owen Andersonaa7f66b2010-07-26 18:48:03 +00001407
Bruno Cardoso Lopes6ac4ea42015-08-18 16:34:27 +00001408 ValueSet.erase(V);
1409 if (ValueSet.empty())
1410 OverDefinedCache.erase(OI);
Owen Andersonaa7f66b2010-07-26 18:48:03 +00001411
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001412 // If we removed anything, then we potentially need to update
Owen Andersonaac5a722010-07-27 23:58:11 +00001413 // blocks successors too.
1414 changed = true;
Owen Andersonaa7f66b2010-07-26 18:48:03 +00001415 }
Nick Lewycky55a700b2010-12-18 01:00:40 +00001416
Owen Andersonaa7f66b2010-07-26 18:48:03 +00001417 if (!changed) continue;
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001418
Owen Andersonaa7f66b2010-07-26 18:48:03 +00001419 worklist.insert(worklist.end(), succ_begin(ToUpdate), succ_end(ToUpdate));
1420 }
1421}
1422
Chris Lattneraf025d32009-11-15 19:59:49 +00001423//===----------------------------------------------------------------------===//
1424// LazyValueInfo Impl
1425//===----------------------------------------------------------------------===//
1426
Sanjay Patel2a385e22015-01-09 16:47:20 +00001427/// This lazily constructs the LazyValueInfoCache.
Chandler Carruth66b31302015-01-04 12:03:27 +00001428static LazyValueInfoCache &getCache(void *&PImpl, AssumptionCache *AC,
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001429 const DataLayout *DL,
Hal Finkel7e184492014-09-07 20:29:59 +00001430 DominatorTree *DT = nullptr) {
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001431 if (!PImpl) {
1432 assert(DL && "getCache() called with a null DataLayout");
1433 PImpl = new LazyValueInfoCache(AC, *DL, DT);
1434 }
Chris Lattneraf025d32009-11-15 19:59:49 +00001435 return *static_cast<LazyValueInfoCache*>(PImpl);
1436}
1437
Owen Anderson208636f2010-08-18 18:39:01 +00001438bool LazyValueInfo::runOnFunction(Function &F) {
Chandler Carruth66b31302015-01-04 12:03:27 +00001439 AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001440 const DataLayout &DL = F.getParent()->getDataLayout();
Hal Finkel7e184492014-09-07 20:29:59 +00001441
1442 DominatorTreeWrapperPass *DTWP =
1443 getAnalysisIfAvailable<DominatorTreeWrapperPass>();
1444 DT = DTWP ? &DTWP->getDomTree() : nullptr;
Chad Rosier43a33062011-12-02 01:26:24 +00001445
Chandler Carruthb98f63d2015-01-15 10:41:28 +00001446 TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
Chad Rosier43a33062011-12-02 01:26:24 +00001447
Hal Finkel7e184492014-09-07 20:29:59 +00001448 if (PImpl)
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001449 getCache(PImpl, AC, &DL, DT).clear();
Hal Finkel7e184492014-09-07 20:29:59 +00001450
Owen Anderson208636f2010-08-18 18:39:01 +00001451 // Fully lazy.
1452 return false;
1453}
1454
Chad Rosier43a33062011-12-02 01:26:24 +00001455void LazyValueInfo::getAnalysisUsage(AnalysisUsage &AU) const {
1456 AU.setPreservesAll();
Chandler Carruth66b31302015-01-04 12:03:27 +00001457 AU.addRequired<AssumptionCacheTracker>();
Chandler Carruthb98f63d2015-01-15 10:41:28 +00001458 AU.addRequired<TargetLibraryInfoWrapperPass>();
Chad Rosier43a33062011-12-02 01:26:24 +00001459}
1460
Chris Lattneraf025d32009-11-15 19:59:49 +00001461void LazyValueInfo::releaseMemory() {
1462 // If the cache was allocated, free it.
1463 if (PImpl) {
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001464 delete &getCache(PImpl, AC, nullptr);
Craig Topper9f008862014-04-15 04:59:12 +00001465 PImpl = nullptr;
Chris Lattneraf025d32009-11-15 19:59:49 +00001466 }
1467}
1468
Hal Finkel7e184492014-09-07 20:29:59 +00001469Constant *LazyValueInfo::getConstant(Value *V, BasicBlock *BB,
1470 Instruction *CxtI) {
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001471 const DataLayout &DL = BB->getModule()->getDataLayout();
Hal Finkel7e184492014-09-07 20:29:59 +00001472 LVILatticeVal Result =
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001473 getCache(PImpl, AC, &DL, DT).getValueInBlock(V, BB, CxtI);
Chandler Carruth66b31302015-01-04 12:03:27 +00001474
Chris Lattner19019ea2009-11-11 22:48:44 +00001475 if (Result.isConstant())
1476 return Result.getConstant();
Nick Lewycky11678bd2010-12-15 18:57:18 +00001477 if (Result.isConstantRange()) {
Owen Anderson38f6b7f2010-08-27 23:29:38 +00001478 ConstantRange CR = Result.getConstantRange();
1479 if (const APInt *SingleVal = CR.getSingleElement())
1480 return ConstantInt::get(V->getContext(), *SingleVal);
1481 }
Craig Topper9f008862014-04-15 04:59:12 +00001482 return nullptr;
Chris Lattner19019ea2009-11-11 22:48:44 +00001483}
Chris Lattnerfde1f8d2009-11-11 02:08:33 +00001484
Sanjay Patel2a385e22015-01-09 16:47:20 +00001485/// Determine whether the specified value is known to be a
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001486/// constant on the specified edge. Return null if not.
Chris Lattnerd5e25432009-11-12 01:29:10 +00001487Constant *LazyValueInfo::getConstantOnEdge(Value *V, BasicBlock *FromBB,
Hal Finkel7e184492014-09-07 20:29:59 +00001488 BasicBlock *ToBB,
1489 Instruction *CxtI) {
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001490 const DataLayout &DL = FromBB->getModule()->getDataLayout();
Hal Finkel7e184492014-09-07 20:29:59 +00001491 LVILatticeVal Result =
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001492 getCache(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
Chandler Carruth66b31302015-01-04 12:03:27 +00001493
Chris Lattnerd5e25432009-11-12 01:29:10 +00001494 if (Result.isConstant())
1495 return Result.getConstant();
Nick Lewycky11678bd2010-12-15 18:57:18 +00001496 if (Result.isConstantRange()) {
Owen Anderson185fe002010-08-10 20:03:09 +00001497 ConstantRange CR = Result.getConstantRange();
1498 if (const APInt *SingleVal = CR.getSingleElement())
1499 return ConstantInt::get(V->getContext(), *SingleVal);
1500 }
Craig Topper9f008862014-04-15 04:59:12 +00001501 return nullptr;
Chris Lattnerd5e25432009-11-12 01:29:10 +00001502}
1503
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001504static LazyValueInfo::Tristate getPredicateResult(unsigned Pred, Constant *C,
1505 LVILatticeVal &Result,
1506 const DataLayout &DL,
1507 TargetLibraryInfo *TLI) {
Hal Finkel7e184492014-09-07 20:29:59 +00001508
Chris Lattner565ee2f2009-11-12 04:36:58 +00001509 // If we know the value is a constant, evaluate the conditional.
Craig Topper9f008862014-04-15 04:59:12 +00001510 Constant *Res = nullptr;
Chris Lattner565ee2f2009-11-12 04:36:58 +00001511 if (Result.isConstant()) {
Rafael Espindola7c68beb2014-02-18 15:33:12 +00001512 Res = ConstantFoldCompareInstOperands(Pred, Result.getConstant(), C, DL,
Chad Rosier43a33062011-12-02 01:26:24 +00001513 TLI);
Nick Lewycky11678bd2010-12-15 18:57:18 +00001514 if (ConstantInt *ResCI = dyn_cast<ConstantInt>(Res))
Hal Finkel7e184492014-09-07 20:29:59 +00001515 return ResCI->isZero() ? LazyValueInfo::False : LazyValueInfo::True;
1516 return LazyValueInfo::Unknown;
Chris Lattneraf025d32009-11-15 19:59:49 +00001517 }
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001518
Owen Anderson185fe002010-08-10 20:03:09 +00001519 if (Result.isConstantRange()) {
Owen Andersonc62f7042010-08-24 07:55:44 +00001520 ConstantInt *CI = dyn_cast<ConstantInt>(C);
Hal Finkel7e184492014-09-07 20:29:59 +00001521 if (!CI) return LazyValueInfo::Unknown;
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001522
Owen Anderson185fe002010-08-10 20:03:09 +00001523 ConstantRange CR = Result.getConstantRange();
1524 if (Pred == ICmpInst::ICMP_EQ) {
1525 if (!CR.contains(CI->getValue()))
Hal Finkel7e184492014-09-07 20:29:59 +00001526 return LazyValueInfo::False;
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001527
Owen Anderson185fe002010-08-10 20:03:09 +00001528 if (CR.isSingleElement() && CR.contains(CI->getValue()))
Hal Finkel7e184492014-09-07 20:29:59 +00001529 return LazyValueInfo::True;
Owen Anderson185fe002010-08-10 20:03:09 +00001530 } else if (Pred == ICmpInst::ICMP_NE) {
1531 if (!CR.contains(CI->getValue()))
Hal Finkel7e184492014-09-07 20:29:59 +00001532 return LazyValueInfo::True;
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001533
Owen Anderson185fe002010-08-10 20:03:09 +00001534 if (CR.isSingleElement() && CR.contains(CI->getValue()))
Hal Finkel7e184492014-09-07 20:29:59 +00001535 return LazyValueInfo::False;
Owen Anderson185fe002010-08-10 20:03:09 +00001536 }
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001537
Owen Anderson185fe002010-08-10 20:03:09 +00001538 // Handle more complex predicates.
Nick Lewycky11678bd2010-12-15 18:57:18 +00001539 ConstantRange TrueValues =
1540 ICmpInst::makeConstantRange((ICmpInst::Predicate)Pred, CI->getValue());
1541 if (TrueValues.contains(CR))
Hal Finkel7e184492014-09-07 20:29:59 +00001542 return LazyValueInfo::True;
Nick Lewycky11678bd2010-12-15 18:57:18 +00001543 if (TrueValues.inverse().contains(CR))
Hal Finkel7e184492014-09-07 20:29:59 +00001544 return LazyValueInfo::False;
1545 return LazyValueInfo::Unknown;
Owen Anderson185fe002010-08-10 20:03:09 +00001546 }
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001547
Chris Lattneraf025d32009-11-15 19:59:49 +00001548 if (Result.isNotConstant()) {
Chris Lattner565ee2f2009-11-12 04:36:58 +00001549 // If this is an equality comparison, we can try to fold it knowing that
1550 // "V != C1".
1551 if (Pred == ICmpInst::ICMP_EQ) {
Sylvestre Ledru91ce36c2012-09-27 10:14:43 +00001552 // !C1 == C -> false iff C1 == C.
Chris Lattner565ee2f2009-11-12 04:36:58 +00001553 Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
Rafael Espindola7c68beb2014-02-18 15:33:12 +00001554 Result.getNotConstant(), C, DL,
Chad Rosier43a33062011-12-02 01:26:24 +00001555 TLI);
Chris Lattner565ee2f2009-11-12 04:36:58 +00001556 if (Res->isNullValue())
Hal Finkel7e184492014-09-07 20:29:59 +00001557 return LazyValueInfo::False;
Chris Lattner565ee2f2009-11-12 04:36:58 +00001558 } else if (Pred == ICmpInst::ICMP_NE) {
Sylvestre Ledru91ce36c2012-09-27 10:14:43 +00001559 // !C1 != C -> true iff C1 == C.
Chris Lattnerb0c0a0d2009-11-15 20:01:24 +00001560 Res = ConstantFoldCompareInstOperands(ICmpInst::ICMP_NE,
Rafael Espindola7c68beb2014-02-18 15:33:12 +00001561 Result.getNotConstant(), C, DL,
Chad Rosier43a33062011-12-02 01:26:24 +00001562 TLI);
Chris Lattner565ee2f2009-11-12 04:36:58 +00001563 if (Res->isNullValue())
Hal Finkel7e184492014-09-07 20:29:59 +00001564 return LazyValueInfo::True;
Chris Lattner565ee2f2009-11-12 04:36:58 +00001565 }
Hal Finkel7e184492014-09-07 20:29:59 +00001566 return LazyValueInfo::Unknown;
Chris Lattner565ee2f2009-11-12 04:36:58 +00001567 }
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001568
Hal Finkel7e184492014-09-07 20:29:59 +00001569 return LazyValueInfo::Unknown;
1570}
1571
Sanjay Patel2a385e22015-01-09 16:47:20 +00001572/// Determine whether the specified value comparison with a constant is known to
1573/// be true or false on the specified CFG edge. Pred is a CmpInst predicate.
Hal Finkel7e184492014-09-07 20:29:59 +00001574LazyValueInfo::Tristate
1575LazyValueInfo::getPredicateOnEdge(unsigned Pred, Value *V, Constant *C,
1576 BasicBlock *FromBB, BasicBlock *ToBB,
1577 Instruction *CxtI) {
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001578 const DataLayout &DL = FromBB->getModule()->getDataLayout();
Hal Finkel7e184492014-09-07 20:29:59 +00001579 LVILatticeVal Result =
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001580 getCache(PImpl, AC, &DL, DT).getValueOnEdge(V, FromBB, ToBB, CxtI);
Hal Finkel7e184492014-09-07 20:29:59 +00001581
1582 return getPredicateResult(Pred, C, Result, DL, TLI);
1583}
1584
1585LazyValueInfo::Tristate
1586LazyValueInfo::getPredicateAt(unsigned Pred, Value *V, Constant *C,
1587 Instruction *CxtI) {
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001588 const DataLayout &DL = CxtI->getModule()->getDataLayout();
1589 LVILatticeVal Result = getCache(PImpl, AC, &DL, DT).getValueAt(V, CxtI);
Philip Reames66ab0f02015-06-16 00:49:59 +00001590 Tristate Ret = getPredicateResult(Pred, C, Result, DL, TLI);
1591 if (Ret != Unknown)
1592 return Ret;
Hal Finkel7e184492014-09-07 20:29:59 +00001593
Philip Reamesaeefae02015-11-04 01:47:04 +00001594 // Note: The following bit of code is somewhat distinct from the rest of LVI;
1595 // LVI as a whole tries to compute a lattice value which is conservatively
1596 // correct at a given location. In this case, we have a predicate which we
1597 // weren't able to prove about the merged result, and we're pushing that
1598 // predicate back along each incoming edge to see if we can prove it
1599 // separately for each input. As a motivating example, consider:
1600 // bb1:
1601 // %v1 = ... ; constantrange<1, 5>
1602 // br label %merge
1603 // bb2:
1604 // %v2 = ... ; constantrange<10, 20>
1605 // br label %merge
1606 // merge:
1607 // %phi = phi [%v1, %v2] ; constantrange<1,20>
1608 // %pred = icmp eq i32 %phi, 8
1609 // We can't tell from the lattice value for '%phi' that '%pred' is false
1610 // along each path, but by checking the predicate over each input separately,
1611 // we can.
1612 // We limit the search to one step backwards from the current BB and value.
1613 // We could consider extending this to search further backwards through the
1614 // CFG and/or value graph, but there are non-obvious compile time vs quality
1615 // tradeoffs.
Philip Reames66ab0f02015-06-16 00:49:59 +00001616 if (CxtI) {
Philip Reamesbb11d622015-08-31 18:31:48 +00001617 BasicBlock *BB = CxtI->getParent();
1618
1619 // Function entry or an unreachable block. Bail to avoid confusing
1620 // analysis below.
1621 pred_iterator PI = pred_begin(BB), PE = pred_end(BB);
1622 if (PI == PE)
1623 return Unknown;
1624
1625 // If V is a PHI node in the same block as the context, we need to ask
1626 // questions about the predicate as applied to the incoming value along
1627 // each edge. This is useful for eliminating cases where the predicate is
1628 // known along all incoming edges.
1629 if (auto *PHI = dyn_cast<PHINode>(V))
1630 if (PHI->getParent() == BB) {
1631 Tristate Baseline = Unknown;
1632 for (unsigned i = 0, e = PHI->getNumIncomingValues(); i < e; i++) {
1633 Value *Incoming = PHI->getIncomingValue(i);
1634 BasicBlock *PredBB = PHI->getIncomingBlock(i);
1635 // Note that PredBB may be BB itself.
1636 Tristate Result = getPredicateOnEdge(Pred, Incoming, C, PredBB, BB,
1637 CxtI);
1638
1639 // Keep going as long as we've seen a consistent known result for
1640 // all inputs.
1641 Baseline = (i == 0) ? Result /* First iteration */
1642 : (Baseline == Result ? Baseline : Unknown); /* All others */
1643 if (Baseline == Unknown)
1644 break;
1645 }
1646 if (Baseline != Unknown)
1647 return Baseline;
1648 }
1649
Philip Reames66ab0f02015-06-16 00:49:59 +00001650 // For a comparison where the V is outside this block, it's possible
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001651 // that we've branched on it before. Look to see if the value is known
Philip Reames66ab0f02015-06-16 00:49:59 +00001652 // on all incoming edges.
Philip Reamesbb11d622015-08-31 18:31:48 +00001653 if (!isa<Instruction>(V) ||
1654 cast<Instruction>(V)->getParent() != BB) {
Philip Reames66ab0f02015-06-16 00:49:59 +00001655 // For predecessor edge, determine if the comparison is true or false
Bruno Cardoso Lopes51fd2422015-07-28 15:53:21 +00001656 // on that edge. If they're all true or all false, we can conclude
Philip Reames66ab0f02015-06-16 00:49:59 +00001657 // the value of the comparison in this block.
1658 Tristate Baseline = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1659 if (Baseline != Unknown) {
1660 // Check that all remaining incoming values match the first one.
1661 while (++PI != PE) {
1662 Tristate Ret = getPredicateOnEdge(Pred, V, C, *PI, BB, CxtI);
1663 if (Ret != Baseline) break;
1664 }
1665 // If we terminated early, then one of the values didn't match.
1666 if (PI == PE) {
1667 return Baseline;
1668 }
1669 }
1670 }
1671 }
1672 return Unknown;
Chris Lattnerfde1f8d2009-11-11 02:08:33 +00001673}
1674
Owen Andersonaa7f66b2010-07-26 18:48:03 +00001675void LazyValueInfo::threadEdge(BasicBlock *PredBB, BasicBlock *OldSucc,
Nick Lewycky11678bd2010-12-15 18:57:18 +00001676 BasicBlock *NewSucc) {
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001677 if (PImpl) {
1678 const DataLayout &DL = PredBB->getModule()->getDataLayout();
1679 getCache(PImpl, AC, &DL, DT).threadEdge(PredBB, OldSucc, NewSucc);
1680 }
Owen Anderson208636f2010-08-18 18:39:01 +00001681}
1682
1683void LazyValueInfo::eraseBlock(BasicBlock *BB) {
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001684 if (PImpl) {
1685 const DataLayout &DL = BB->getModule()->getDataLayout();
1686 getCache(PImpl, AC, &DL, DT).eraseBlock(BB);
1687 }
Owen Andersonaa7f66b2010-07-26 18:48:03 +00001688}