blob: 55498432e119ed2f54e2f7be0e2f182fadc54279 [file] [log] [blame]
Dan Gohmanda85ed82010-10-19 23:09:08 +00001//===- BasicAliasAnalysis.cpp - Stateless Alias Analysis Impl -------------===//
Misha Brukman01808ca2005-04-21 21:13:18 +00002//
John Criswell482202a2003-10-20 19:43:21 +00003// The LLVM Compiler Infrastructure
4//
Chris Lattnerf3ebc3f2007-12-29 20:36:04 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Misha Brukman01808ca2005-04-21 21:13:18 +00007//
John Criswell482202a2003-10-20 19:43:21 +00008//===----------------------------------------------------------------------===//
Chris Lattnerd6a2a992003-02-26 19:41:54 +00009//
Dan Gohmanda85ed82010-10-19 23:09:08 +000010// This file defines the primary stateless implementation of the
11// Alias Analysis interface that implements identities (two different
12// globals cannot alias, etc), but does no stateful analysis.
Chris Lattnerd6a2a992003-02-26 19:41:54 +000013//
14//===----------------------------------------------------------------------===//
15
Chandler Carruth17e0bc32015-08-06 07:33:15 +000016#include "llvm/Analysis/BasicAliasAnalysis.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000017#include "llvm/ADT/SmallVector.h"
Wei Mid67daae2015-08-05 23:40:30 +000018#include "llvm/ADT/Statistic.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000019#include "llvm/Analysis/AliasAnalysis.h"
Arnold Schwaighofer833a82e2014-01-03 05:47:03 +000020#include "llvm/Analysis/CFG.h"
Chandler Carruth8a8cd2b2014-01-07 11:48:04 +000021#include "llvm/Analysis/CaptureTracking.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000022#include "llvm/Analysis/InstructionSimplify.h"
Arnold Schwaighofer833a82e2014-01-03 05:47:03 +000023#include "llvm/Analysis/LoopInfo.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000024#include "llvm/Analysis/MemoryBuiltins.h"
25#include "llvm/Analysis/ValueTracking.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000026#include "llvm/IR/Constants.h"
27#include "llvm/IR/DataLayout.h"
28#include "llvm/IR/DerivedTypes.h"
Chandler Carruth5ad5f152014-01-13 09:26:24 +000029#include "llvm/IR/Dominators.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000030#include "llvm/IR/GlobalAlias.h"
31#include "llvm/IR/GlobalVariable.h"
32#include "llvm/IR/Instructions.h"
33#include "llvm/IR/IntrinsicInst.h"
34#include "llvm/IR/LLVMContext.h"
35#include "llvm/IR/Operator.h"
Chris Lattnerd82256a2004-03-15 03:36:49 +000036#include "llvm/Pass.h"
Torok Edwin56d06592009-07-11 20:10:48 +000037#include "llvm/Support/ErrorHandling.h"
Alkis Evlogimenosa5c04ee2004-09-03 18:19:51 +000038#include <algorithm>
Gerolf Hoflehner1d1fbb52016-01-30 02:42:11 +000039
40#define DEBUG_TYPE "basicaa"
41
Chris Lattner35997482003-11-25 18:33:40 +000042using namespace llvm;
Brian Gaeke960707c2003-11-11 22:41:34 +000043
Tobias Edler von Kochd8ce16b2015-07-15 19:32:22 +000044/// Enable analysis of recursive PHI nodes.
Chandler Carruth903c5f92015-08-06 07:57:58 +000045static cl::opt<bool> EnableRecPhiAnalysis("basicaa-recphi", cl::Hidden,
46 cl::init(false));
Wei Mid67daae2015-08-05 23:40:30 +000047/// SearchLimitReached / SearchTimes shows how often the limit of
48/// to decompose GEPs is reached. It will affect the precision
49/// of basic alias analysis.
Wei Mid67daae2015-08-05 23:40:30 +000050STATISTIC(SearchLimitReached, "Number of times the limit to "
51 "decompose GEPs is reached");
52STATISTIC(SearchTimes, "Number of times a GEP is decomposed");
53
Arnold Schwaighofer0d10a9d2014-01-02 03:31:36 +000054/// Cutoff after which to stop analysing a set of phi nodes potentially involved
Sanjay Patel9613b292016-01-17 23:13:48 +000055/// in a cycle. Because we are analysing 'through' phi nodes, we need to be
Arnold Schwaighofer833a82e2014-01-03 05:47:03 +000056/// careful with value equivalence. We use reachability to make sure a value
57/// cannot be involved in a cycle.
58const unsigned MaxNumPhiBBsValueReachabilityCheck = 20;
Arnold Schwaighofer0d10a9d2014-01-02 03:31:36 +000059
Arnold Schwaighofer1a444482014-03-26 21:30:19 +000060// The max limit of the search depth in DecomposeGEPExpression() and
61// GetUnderlyingObject(), both functions need to use the same search
62// depth otherwise the algorithm in aliasGEP will assert.
63static const unsigned MaxLookupSearchDepth = 6;
64
Chris Lattner2d332972008-06-16 06:30:22 +000065//===----------------------------------------------------------------------===//
66// Useful predicates
67//===----------------------------------------------------------------------===//
Devang Patel09f162c2007-05-01 21:15:47 +000068
Chandler Carruthc5d81122015-08-06 08:17:06 +000069/// Returns true if the pointer is to a function-local object that never
70/// escapes from the function.
Dan Gohman84f90a32010-07-01 20:08:40 +000071static bool isNonEscapingLocalObject(const Value *V) {
Chris Lattnerfa482582008-06-16 06:28:01 +000072 // If this is a local allocation, check to see if it escapes.
Dan Gohman84f90a32010-07-01 20:08:40 +000073 if (isa<AllocaInst>(V) || isNoAliasCall(V))
Dan Gohman94e61762009-11-19 21:57:48 +000074 // Set StoreCaptures to True so that we can assume in our callers that the
75 // pointer is not the result of a load instruction. Currently
76 // PointerMayBeCaptured doesn't have any special analysis for the
77 // StoreCaptures=false case; if it did, our callers could be refined to be
78 // more precise.
79 return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true);
Duncan Sands8d65f362009-01-05 21:19:53 +000080
Chris Lattnerfa482582008-06-16 06:28:01 +000081 // If this is an argument that corresponds to a byval or noalias argument,
Duncan Sands8d65f362009-01-05 21:19:53 +000082 // then it has not escaped before entering the function. Check if it escapes
83 // inside the function.
Dan Gohman84f90a32010-07-01 20:08:40 +000084 if (const Argument *A = dyn_cast<Argument>(V))
Richard Osbornea1fffcf2012-11-05 10:48:24 +000085 if (A->hasByValAttr() || A->hasNoAliasAttr())
Sanjay Patel9613b292016-01-17 23:13:48 +000086 // Note even if the argument is marked nocapture, we still need to check
Richard Osbornea1fffcf2012-11-05 10:48:24 +000087 // for copies made inside the function. The nocapture attribute only
88 // specifies that there are no copies made that outlive the function.
Dan Gohman84f90a32010-07-01 20:08:40 +000089 return !PointerMayBeCaptured(V, false, /*StoreCaptures=*/true);
Richard Osbornea1fffcf2012-11-05 10:48:24 +000090
Chris Lattnerb35d9b52008-06-16 06:19:11 +000091 return false;
92}
93
Chandler Carruthc5d81122015-08-06 08:17:06 +000094/// Returns true if the pointer is one which would have been considered an
95/// escape by isNonEscapingLocalObject.
Dan Gohman84f90a32010-07-01 20:08:40 +000096static bool isEscapeSource(const Value *V) {
97 if (isa<CallInst>(V) || isa<InvokeInst>(V) || isa<Argument>(V))
98 return true;
Dan Gohman0824aff2010-06-29 00:50:39 +000099
100 // The load case works because isNonEscapingLocalObject considers all
101 // stores to be escapes (it passes true for the StoreCaptures argument
102 // to PointerMayBeCaptured).
103 if (isa<LoadInst>(V))
104 return true;
105
106 return false;
107}
Chris Lattnerb35d9b52008-06-16 06:19:11 +0000108
Sanjay Patel9613b292016-01-17 23:13:48 +0000109/// Returns the size of the object specified by V or UnknownSize if unknown.
Rafael Espindola5f57f462014-02-21 18:34:28 +0000110static uint64_t getObjectSize(const Value *V, const DataLayout &DL,
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000111 const TargetLibraryInfo &TLI,
Eli Friedman8bc169c2012-02-27 20:46:07 +0000112 bool RoundToAlign = false) {
Nuno Lopes55fff832012-06-21 15:45:28 +0000113 uint64_t Size;
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000114 if (getObjectSize(V, Size, DL, &TLI, RoundToAlign))
Nuno Lopes55fff832012-06-21 15:45:28 +0000115 return Size;
Chandler Carruthecbd1682015-06-17 07:21:38 +0000116 return MemoryLocation::UnknownSize;
Dan Gohman44da55b2011-01-18 21:16:06 +0000117}
118
Chandler Carruthc5d81122015-08-06 08:17:06 +0000119/// Returns true if we can prove that the object specified by V is smaller than
120/// Size.
Dan Gohman44da55b2011-01-18 21:16:06 +0000121static bool isObjectSmallerThan(const Value *V, uint64_t Size,
Rafael Espindola5f57f462014-02-21 18:34:28 +0000122 const DataLayout &DL,
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000123 const TargetLibraryInfo &TLI) {
Nadav Rotemabcc64f2013-04-09 18:16:05 +0000124 // Note that the meanings of the "object" are slightly different in the
125 // following contexts:
126 // c1: llvm::getObjectSize()
127 // c2: llvm.objectsize() intrinsic
128 // c3: isObjectSmallerThan()
129 // c1 and c2 share the same meaning; however, the meaning of "object" in c3
130 // refers to the "entire object".
131 //
132 // Consider this example:
133 // char *p = (char*)malloc(100)
134 // char *q = p+80;
135 //
136 // In the context of c1 and c2, the "object" pointed by q refers to the
137 // stretch of memory of q[0:19]. So, getObjectSize(q) should return 20.
138 //
139 // However, in the context of c3, the "object" refers to the chunk of memory
140 // being allocated. So, the "object" has 100 bytes, and q points to the middle
141 // the "object". In case q is passed to isObjectSmallerThan() as the 1st
142 // parameter, before the llvm::getObjectSize() is called to get the size of
143 // entire object, we should:
144 // - either rewind the pointer q to the base-address of the object in
145 // question (in this case rewind to p), or
146 // - just give up. It is up to caller to make sure the pointer is pointing
147 // to the base address the object.
Jakub Staszak07f383f2013-08-24 14:16:00 +0000148 //
Nadav Rotemabcc64f2013-04-09 18:16:05 +0000149 // We go for 2nd option for simplicity.
150 if (!isIdentifiedObject(V))
151 return false;
152
Eli Friedman8bc169c2012-02-27 20:46:07 +0000153 // This function needs to use the aligned object size because we allow
154 // reads a bit past the end given sufficient alignment.
Chandler Carruth903c5f92015-08-06 07:57:58 +0000155 uint64_t ObjectSize = getObjectSize(V, DL, TLI, /*RoundToAlign*/ true);
Jakub Staszak07f383f2013-08-24 14:16:00 +0000156
Chandler Carruthecbd1682015-06-17 07:21:38 +0000157 return ObjectSize != MemoryLocation::UnknownSize && ObjectSize < Size;
Dan Gohman44da55b2011-01-18 21:16:06 +0000158}
159
Chandler Carruthc5d81122015-08-06 08:17:06 +0000160/// Returns true if we can prove that the object specified by V has size Size.
Chandler Carruth903c5f92015-08-06 07:57:58 +0000161static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &DL,
162 const TargetLibraryInfo &TLI) {
Rafael Espindola5f57f462014-02-21 18:34:28 +0000163 uint64_t ObjectSize = getObjectSize(V, DL, TLI);
Chandler Carruthecbd1682015-06-17 07:21:38 +0000164 return ObjectSize != MemoryLocation::UnknownSize && ObjectSize == Size;
Chris Lattner98ad8162008-06-16 06:10:11 +0000165}
166
Chris Lattner2d332972008-06-16 06:30:22 +0000167//===----------------------------------------------------------------------===//
Chris Lattner9f7500f2010-08-18 22:07:29 +0000168// GetElementPtr Instruction Decomposition and Analysis
169//===----------------------------------------------------------------------===//
170
Chandler Carruthc5d81122015-08-06 08:17:06 +0000171/// Analyzes the specified value as a linear expression: "A*V + B", where A and
172/// B are constant integers.
173///
174/// Returns the scale and offset values as APInts and return V as a Value*, and
175/// return whether we looked through any sign or zero extends. The incoming
Sanjay Patel9613b292016-01-17 23:13:48 +0000176/// Value is known to have IntegerType, and it may already be sign or zero
Chandler Carruthc5d81122015-08-06 08:17:06 +0000177/// extended.
Chris Lattner3decde92010-08-18 23:09:49 +0000178///
179/// Note that this looks through extends, so the high bits may not be
180/// represented in the result.
Chandler Carruth7b560d42015-09-09 17:55:00 +0000181/*static*/ const Value *BasicAAResult::GetLinearExpression(
Quentin Colombet5989bc62015-08-31 22:32:47 +0000182 const Value *V, APInt &Scale, APInt &Offset, unsigned &ZExtBits,
183 unsigned &SExtBits, const DataLayout &DL, unsigned Depth,
Hal Finkel3ca4a6b2016-12-15 03:02:15 +0000184 DominatorTree *DT, bool &NSW, bool &NUW) {
Chris Lattner9f7500f2010-08-18 22:07:29 +0000185 assert(V->getType()->isIntegerTy() && "Not an integer value");
186
187 // Limit our recursion depth.
188 if (Depth == 6) {
189 Scale = 1;
190 Offset = 0;
191 return V;
192 }
Jakub Staszak07f383f2013-08-24 14:16:00 +0000193
Quentin Colombet5989bc62015-08-31 22:32:47 +0000194 if (const ConstantInt *Const = dyn_cast<ConstantInt>(V)) {
Sanjay Patel9613b292016-01-17 23:13:48 +0000195 // If it's a constant, just convert it to an offset and remove the variable.
196 // If we've been called recursively, the Offset bit width will be greater
Quentin Colombet5989bc62015-08-31 22:32:47 +0000197 // than the constant's (the Offset's always as wide as the outermost call),
198 // so we'll zext here and process any extension in the isa<SExtInst> &
199 // isa<ZExtInst> cases below.
200 Offset += Const->getValue().zextOrSelf(Offset.getBitWidth());
201 assert(Scale == 0 && "Constant values don't have a scale");
202 return V;
203 }
204
205 if (const BinaryOperator *BOp = dyn_cast<BinaryOperator>(V)) {
Chris Lattner9f7500f2010-08-18 22:07:29 +0000206 if (ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) {
Quentin Colombet5989bc62015-08-31 22:32:47 +0000207
Sanjay Patel9613b292016-01-17 23:13:48 +0000208 // If we've been called recursively, then Offset and Scale will be wider
209 // than the BOp operands. We'll always zext it here as we'll process sign
Quentin Colombet5989bc62015-08-31 22:32:47 +0000210 // extensions below (see the isa<SExtInst> / isa<ZExtInst> cases).
211 APInt RHS = RHSC->getValue().zextOrSelf(Offset.getBitWidth());
212
Chris Lattner9f7500f2010-08-18 22:07:29 +0000213 switch (BOp->getOpcode()) {
Chandler Carruth903c5f92015-08-06 07:57:58 +0000214 default:
Quentin Colombet5989bc62015-08-31 22:32:47 +0000215 // We don't understand this instruction, so we can't decompose it any
216 // further.
217 Scale = 1;
218 Offset = 0;
219 return V;
Chris Lattner9f7500f2010-08-18 22:07:29 +0000220 case Instruction::Or:
221 // X|C == X+C if all the bits in C are unset in X. Otherwise we can't
222 // analyze it.
Hal Finkel3ca4a6b2016-12-15 03:02:15 +0000223 if (!MaskedValueIsZero(BOp->getOperand(0), RHSC->getValue(), DL, 0,
Quentin Colombet5989bc62015-08-31 22:32:47 +0000224 BOp, DT)) {
225 Scale = 1;
226 Offset = 0;
227 return V;
228 }
Justin Bognercd1d5aa2016-08-17 20:30:52 +0000229 LLVM_FALLTHROUGH;
Chris Lattner9f7500f2010-08-18 22:07:29 +0000230 case Instruction::Add:
Quentin Colombet5989bc62015-08-31 22:32:47 +0000231 V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits,
Hal Finkel3ca4a6b2016-12-15 03:02:15 +0000232 SExtBits, DL, Depth + 1, DT, NSW, NUW);
Quentin Colombet5989bc62015-08-31 22:32:47 +0000233 Offset += RHS;
234 break;
235 case Instruction::Sub:
236 V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits,
Hal Finkel3ca4a6b2016-12-15 03:02:15 +0000237 SExtBits, DL, Depth + 1, DT, NSW, NUW);
Quentin Colombet5989bc62015-08-31 22:32:47 +0000238 Offset -= RHS;
239 break;
Chris Lattner9f7500f2010-08-18 22:07:29 +0000240 case Instruction::Mul:
Quentin Colombet5989bc62015-08-31 22:32:47 +0000241 V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits,
Hal Finkel3ca4a6b2016-12-15 03:02:15 +0000242 SExtBits, DL, Depth + 1, DT, NSW, NUW);
Quentin Colombet5989bc62015-08-31 22:32:47 +0000243 Offset *= RHS;
244 Scale *= RHS;
245 break;
Chris Lattner9f7500f2010-08-18 22:07:29 +0000246 case Instruction::Shl:
Quentin Colombet5989bc62015-08-31 22:32:47 +0000247 V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits,
Hal Finkel3ca4a6b2016-12-15 03:02:15 +0000248 SExtBits, DL, Depth + 1, DT, NSW, NUW);
Quentin Colombet5989bc62015-08-31 22:32:47 +0000249 Offset <<= RHS.getLimitedValue();
250 Scale <<= RHS.getLimitedValue();
251 // the semantics of nsw and nuw for left shifts don't match those of
252 // multiplications, so we won't propagate them.
253 NSW = NUW = false;
Chris Lattner9f7500f2010-08-18 22:07:29 +0000254 return V;
255 }
Quentin Colombet5989bc62015-08-31 22:32:47 +0000256
257 if (isa<OverflowingBinaryOperator>(BOp)) {
258 NUW &= BOp->hasNoUnsignedWrap();
259 NSW &= BOp->hasNoSignedWrap();
260 }
261 return V;
Chris Lattner9f7500f2010-08-18 22:07:29 +0000262 }
263 }
Jakub Staszak07f383f2013-08-24 14:16:00 +0000264
Chris Lattner9f7500f2010-08-18 22:07:29 +0000265 // Since GEP indices are sign extended anyway, we don't care about the high
Chris Lattner3decde92010-08-18 23:09:49 +0000266 // bits of a sign or zero extended value - just scales and offsets. The
267 // extensions have to be consistent though.
Quentin Colombet5989bc62015-08-31 22:32:47 +0000268 if (isa<SExtInst>(V) || isa<ZExtInst>(V)) {
Chris Lattner9f7500f2010-08-18 22:07:29 +0000269 Value *CastOp = cast<CastInst>(V)->getOperand(0);
Quentin Colombet5989bc62015-08-31 22:32:47 +0000270 unsigned NewWidth = V->getType()->getPrimitiveSizeInBits();
Chris Lattner9f7500f2010-08-18 22:07:29 +0000271 unsigned SmallWidth = CastOp->getType()->getPrimitiveSizeInBits();
Quentin Colombet5989bc62015-08-31 22:32:47 +0000272 unsigned OldZExtBits = ZExtBits, OldSExtBits = SExtBits;
273 const Value *Result =
274 GetLinearExpression(CastOp, Scale, Offset, ZExtBits, SExtBits, DL,
Hal Finkel3ca4a6b2016-12-15 03:02:15 +0000275 Depth + 1, DT, NSW, NUW);
Chris Lattner3decde92010-08-18 23:09:49 +0000276
Simon Pilgrimf2fbf432016-11-20 13:47:59 +0000277 // zext(zext(%x)) == zext(%x), and similarly for sext; we'll handle this
Quentin Colombet5989bc62015-08-31 22:32:47 +0000278 // by just incrementing the number of bits we've extended by.
279 unsigned ExtendedBy = NewWidth - SmallWidth;
280
281 if (isa<SExtInst>(V) && ZExtBits == 0) {
282 // sext(sext(%x, a), b) == sext(%x, a + b)
283
284 if (NSW) {
285 // We haven't sign-wrapped, so it's valid to decompose sext(%x + c)
286 // into sext(%x) + sext(c). We'll sext the Offset ourselves:
287 unsigned OldWidth = Offset.getBitWidth();
288 Offset = Offset.trunc(SmallWidth).sext(NewWidth).zextOrSelf(OldWidth);
289 } else {
290 // We may have signed-wrapped, so don't decompose sext(%x + c) into
291 // sext(%x) + sext(c)
292 Scale = 1;
293 Offset = 0;
294 Result = CastOp;
295 ZExtBits = OldZExtBits;
296 SExtBits = OldSExtBits;
297 }
298 SExtBits += ExtendedBy;
299 } else {
300 // sext(zext(%x, a), b) = zext(zext(%x, a), b) = zext(%x, a + b)
301
302 if (!NUW) {
303 // We may have unsigned-wrapped, so don't decompose zext(%x + c) into
304 // zext(%x) + zext(c)
305 Scale = 1;
306 Offset = 0;
307 Result = CastOp;
308 ZExtBits = OldZExtBits;
309 SExtBits = OldSExtBits;
310 }
311 ZExtBits += ExtendedBy;
312 }
Jakub Staszak07f383f2013-08-24 14:16:00 +0000313
Chris Lattner9f7500f2010-08-18 22:07:29 +0000314 return Result;
315 }
Jakub Staszak07f383f2013-08-24 14:16:00 +0000316
Chris Lattner9f7500f2010-08-18 22:07:29 +0000317 Scale = 1;
318 Offset = 0;
319 return V;
320}
321
Gerolf Hoflehner1d1fbb52016-01-30 02:42:11 +0000322/// To ensure a pointer offset fits in an integer of size PointerSize
323/// (in bits) when that size is smaller than 64. This is an issue in
324/// particular for 32b programs with negative indices that rely on two's
Gerolf Hoflehnerd24671f2016-01-30 05:58:38 +0000325/// complement wrap-arounds for precise alias information.
Gerolf Hoflehner1d1fbb52016-01-30 02:42:11 +0000326static int64_t adjustToPointerSize(int64_t Offset, unsigned PointerSize) {
327 assert(PointerSize <= 64 && "Invalid PointerSize!");
328 unsigned ShiftBits = 64 - PointerSize;
Gerolf Hoflehner73fc84b2016-01-30 05:35:09 +0000329 return (int64_t)((uint64_t)Offset << ShiftBits) >> ShiftBits;
Gerolf Hoflehner1d1fbb52016-01-30 02:42:11 +0000330}
331
Chandler Carruthc5d81122015-08-06 08:17:06 +0000332/// If V is a symbolic pointer expression, decompose it into a base pointer
333/// with a constant offset and a number of scaled symbolic offsets.
Chris Lattner9f7500f2010-08-18 22:07:29 +0000334///
Chandler Carruthc5d81122015-08-06 08:17:06 +0000335/// The scaled symbolic offsets (represented by pairs of a Value* and a scale
336/// in the VarIndices vector) are Value*'s that are known to be scaled by the
337/// specified amount, but which may have other unrepresented high bits. As
338/// such, the gep cannot necessarily be reconstructed from its decomposed form.
Chris Lattner9f7500f2010-08-18 22:07:29 +0000339///
Micah Villmowcdfe20b2012-10-08 16:38:25 +0000340/// When DataLayout is around, this function is capable of analyzing everything
Arnold Schwaighofer1a444482014-03-26 21:30:19 +0000341/// that GetUnderlyingObject can look through. To be able to do that
342/// GetUnderlyingObject and DecomposeGEPExpression must use the same search
Chandler Carruthc5d81122015-08-06 08:17:06 +0000343/// depth (MaxLookupSearchDepth). When DataLayout not is around, it just looks
344/// through pointer casts.
Michael Kuperstein82069c42016-05-25 22:23:08 +0000345bool BasicAAResult::DecomposeGEPExpression(const Value *V,
Hal Finkel3ca4a6b2016-12-15 03:02:15 +0000346 DecomposedGEP &Decomposed, const DataLayout &DL,
Michael Kuperstein82069c42016-05-25 22:23:08 +0000347 DominatorTree *DT) {
Chris Lattner9f7500f2010-08-18 22:07:29 +0000348 // Limit recursion depth to limit compile time in crazy cases.
Arnold Schwaighofer1a444482014-03-26 21:30:19 +0000349 unsigned MaxLookup = MaxLookupSearchDepth;
Wei Mid67daae2015-08-05 23:40:30 +0000350 SearchTimes++;
Jakub Staszak07f383f2013-08-24 14:16:00 +0000351
Michael Kuperstein82069c42016-05-25 22:23:08 +0000352 Decomposed.StructOffset = 0;
353 Decomposed.OtherOffset = 0;
354 Decomposed.VarIndices.clear();
Chris Lattner9f7500f2010-08-18 22:07:29 +0000355 do {
356 // See if this is a bitcast or GEP.
357 const Operator *Op = dyn_cast<Operator>(V);
Craig Topper9f008862014-04-15 04:59:12 +0000358 if (!Op) {
Chris Lattner9f7500f2010-08-18 22:07:29 +0000359 // The only non-operator case we can handle are GlobalAliases.
360 if (const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
Sanjoy Das5ce32722016-04-08 00:48:30 +0000361 if (!GA->isInterposable()) {
Chris Lattner9f7500f2010-08-18 22:07:29 +0000362 V = GA->getAliasee();
363 continue;
364 }
365 }
Michael Kuperstein82069c42016-05-25 22:23:08 +0000366 Decomposed.Base = V;
367 return false;
Chris Lattner9f7500f2010-08-18 22:07:29 +0000368 }
Jakub Staszak07f383f2013-08-24 14:16:00 +0000369
Matt Arsenault70f4db882014-07-15 00:56:40 +0000370 if (Op->getOpcode() == Instruction::BitCast ||
371 Op->getOpcode() == Instruction::AddrSpaceCast) {
Chris Lattner9f7500f2010-08-18 22:07:29 +0000372 V = Op->getOperand(0);
373 continue;
374 }
Dan Gohman05b18f12010-12-15 20:49:55 +0000375
Chris Lattner9f7500f2010-08-18 22:07:29 +0000376 const GEPOperator *GEPOp = dyn_cast<GEPOperator>(Op);
Craig Topper9f008862014-04-15 04:59:12 +0000377 if (!GEPOp) {
Hal Finkel5c12d8f2016-07-11 01:32:20 +0000378 if (auto CS = ImmutableCallSite(V))
379 if (const Value *RV = CS.getReturnedArgOperand()) {
380 V = RV;
381 continue;
382 }
383
Dan Gohman0573b552011-05-24 18:24:08 +0000384 // If it's not a GEP, hand it off to SimplifyInstruction to see if it
385 // can come up with something. This matches what GetUnderlyingObject does.
386 if (const Instruction *I = dyn_cast<Instruction>(V))
Hal Finkel3ca4a6b2016-12-15 03:02:15 +0000387 // TODO: Get a DominatorTree and use it here (it is now available in
388 // this function, but this should be updated when GetUnderlyingObject
389 // is updated). TLI should be provided also.
Dan Gohman0573b552011-05-24 18:24:08 +0000390 if (const Value *Simplified =
Chandler Carruth903c5f92015-08-06 07:57:58 +0000391 SimplifyInstruction(const_cast<Instruction *>(I), DL)) {
Dan Gohman0573b552011-05-24 18:24:08 +0000392 V = Simplified;
393 continue;
394 }
Jakub Staszak07f383f2013-08-24 14:16:00 +0000395
Michael Kuperstein82069c42016-05-25 22:23:08 +0000396 Decomposed.Base = V;
397 return false;
Dan Gohman0573b552011-05-24 18:24:08 +0000398 }
Jakub Staszak07f383f2013-08-24 14:16:00 +0000399
Chris Lattner9f7500f2010-08-18 22:07:29 +0000400 // Don't attempt to analyze GEPs over unsized objects.
Michael Kuperstein82069c42016-05-25 22:23:08 +0000401 if (!GEPOp->getSourceElementType()->isSized()) {
402 Decomposed.Base = V;
403 return false;
404 }
Jakub Staszak07f383f2013-08-24 14:16:00 +0000405
Matt Arsenaulta8fe22b2013-11-16 00:36:43 +0000406 unsigned AS = GEPOp->getPointerAddressSpace();
Chris Lattner9f7500f2010-08-18 22:07:29 +0000407 // Walk the indices of the GEP, accumulating them into BaseOff/VarIndices.
408 gep_type_iterator GTI = gep_type_begin(GEPOp);
Gerolf Hoflehner1d1fbb52016-01-30 02:42:11 +0000409 unsigned PointerSize = DL.getPointerSizeInBits(AS);
Gerolf Hoflehner9e2afa82016-10-22 02:41:39 +0000410 // Assume all GEP operands are constants until proven otherwise.
411 bool GepHasConstantOffset = true;
Chandler Carruth903c5f92015-08-06 07:57:58 +0000412 for (User::const_op_iterator I = GEPOp->op_begin() + 1, E = GEPOp->op_end();
Peter Collingbourneab85225b2016-12-02 02:24:42 +0000413 I != E; ++I, ++GTI) {
Quentin Colombet5989bc62015-08-31 22:32:47 +0000414 const Value *Index = *I;
Chris Lattner9f7500f2010-08-18 22:07:29 +0000415 // Compute the (potentially symbolic) offset in bytes for this index.
Peter Collingbourneab85225b2016-12-02 02:24:42 +0000416 if (StructType *STy = GTI.getStructTypeOrNull()) {
Chris Lattner9f7500f2010-08-18 22:07:29 +0000417 // For a struct, add the member offset.
418 unsigned FieldNo = cast<ConstantInt>(Index)->getZExtValue();
Chandler Carruth903c5f92015-08-06 07:57:58 +0000419 if (FieldNo == 0)
420 continue;
Jakub Staszak07f383f2013-08-24 14:16:00 +0000421
Michael Kuperstein82069c42016-05-25 22:23:08 +0000422 Decomposed.StructOffset +=
423 DL.getStructLayout(STy)->getElementOffset(FieldNo);
Chris Lattner9f7500f2010-08-18 22:07:29 +0000424 continue;
425 }
Jakub Staszak07f383f2013-08-24 14:16:00 +0000426
Chris Lattner9f7500f2010-08-18 22:07:29 +0000427 // For an array/pointer, add the element offset, explicitly scaled.
Quentin Colombet5989bc62015-08-31 22:32:47 +0000428 if (const ConstantInt *CIdx = dyn_cast<ConstantInt>(Index)) {
Chandler Carruth903c5f92015-08-06 07:57:58 +0000429 if (CIdx->isZero())
430 continue;
Michael Kuperstein82069c42016-05-25 22:23:08 +0000431 Decomposed.OtherOffset +=
Peter Collingbourneab85225b2016-12-02 02:24:42 +0000432 DL.getTypeAllocSize(GTI.getIndexedType()) * CIdx->getSExtValue();
Chris Lattner9f7500f2010-08-18 22:07:29 +0000433 continue;
434 }
Jakub Staszak07f383f2013-08-24 14:16:00 +0000435
Gerolf Hoflehner9e2afa82016-10-22 02:41:39 +0000436 GepHasConstantOffset = false;
437
Peter Collingbourneab85225b2016-12-02 02:24:42 +0000438 uint64_t Scale = DL.getTypeAllocSize(GTI.getIndexedType());
Quentin Colombet5989bc62015-08-31 22:32:47 +0000439 unsigned ZExtBits = 0, SExtBits = 0;
Jakub Staszak07f383f2013-08-24 14:16:00 +0000440
Chris Lattner3decde92010-08-18 23:09:49 +0000441 // If the integer type is smaller than the pointer size, it is implicitly
442 // sign extended to pointer size.
Matt Arsenaultfa252722013-09-27 22:18:51 +0000443 unsigned Width = Index->getType()->getIntegerBitWidth();
Quentin Colombet5989bc62015-08-31 22:32:47 +0000444 if (PointerSize > Width)
445 SExtBits += PointerSize - Width;
Jakub Staszak07f383f2013-08-24 14:16:00 +0000446
Chris Lattner3decde92010-08-18 23:09:49 +0000447 // Use GetLinearExpression to decompose the index into a C1*V+C2 form.
Chris Lattner9f7500f2010-08-18 22:07:29 +0000448 APInt IndexScale(Width, 0), IndexOffset(Width, 0);
Quentin Colombet5989bc62015-08-31 22:32:47 +0000449 bool NSW = true, NUW = true;
450 Index = GetLinearExpression(Index, IndexScale, IndexOffset, ZExtBits,
Hal Finkel3ca4a6b2016-12-15 03:02:15 +0000451 SExtBits, DL, 0, DT, NSW, NUW);
Jakub Staszak07f383f2013-08-24 14:16:00 +0000452
Chris Lattner9f7500f2010-08-18 22:07:29 +0000453 // The GEP index scale ("Scale") scales C1*V+C2, yielding (C1*V+C2)*Scale.
454 // This gives us an aggregate computation of (C1*Scale)*V + C2*Scale.
Michael Kuperstein82069c42016-05-25 22:23:08 +0000455 Decomposed.OtherOffset += IndexOffset.getSExtValue() * Scale;
Eli Friedmanab3a1282010-09-15 20:08:03 +0000456 Scale *= IndexScale.getSExtValue();
Jakub Staszak07f383f2013-08-24 14:16:00 +0000457
Chris Lattner0ab5e2c2011-04-15 05:18:47 +0000458 // If we already had an occurrence of this index variable, merge this
Chris Lattner9f7500f2010-08-18 22:07:29 +0000459 // scale into it. For example, we want to handle:
460 // A[x][x] -> x*16 + x*4 -> x*20
461 // This also ensures that 'x' only appears in the index list once.
Michael Kuperstein82069c42016-05-25 22:23:08 +0000462 for (unsigned i = 0, e = Decomposed.VarIndices.size(); i != e; ++i) {
Gerolf Hoflehner9e2afa82016-10-22 02:41:39 +0000463 if (Decomposed.VarIndices[i].V == Index &&
Michael Kuperstein82069c42016-05-25 22:23:08 +0000464 Decomposed.VarIndices[i].ZExtBits == ZExtBits &&
465 Decomposed.VarIndices[i].SExtBits == SExtBits) {
466 Scale += Decomposed.VarIndices[i].Scale;
467 Decomposed.VarIndices.erase(Decomposed.VarIndices.begin() + i);
Chris Lattner9f7500f2010-08-18 22:07:29 +0000468 break;
469 }
470 }
Jakub Staszak07f383f2013-08-24 14:16:00 +0000471
Chris Lattner9f7500f2010-08-18 22:07:29 +0000472 // Make sure that we have a scale that makes sense for this target's
473 // pointer size.
Gerolf Hoflehner1d1fbb52016-01-30 02:42:11 +0000474 Scale = adjustToPointerSize(Scale, PointerSize);
Jakub Staszak07f383f2013-08-24 14:16:00 +0000475
Chris Lattner1b9c3872010-08-18 22:47:56 +0000476 if (Scale) {
Quentin Colombet5989bc62015-08-31 22:32:47 +0000477 VariableGEPIndex Entry = {Index, ZExtBits, SExtBits,
Jeffrey Yasskin6381c012011-07-27 06:22:51 +0000478 static_cast<int64_t>(Scale)};
Michael Kuperstein82069c42016-05-25 22:23:08 +0000479 Decomposed.VarIndices.push_back(Entry);
Chris Lattner1b9c3872010-08-18 22:47:56 +0000480 }
Chris Lattner9f7500f2010-08-18 22:07:29 +0000481 }
Jakub Staszak07f383f2013-08-24 14:16:00 +0000482
Gerolf Hoflehner87ddb652016-01-30 05:52:53 +0000483 // Take care of wrap-arounds
Gerolf Hoflehner9e2afa82016-10-22 02:41:39 +0000484 if (GepHasConstantOffset) {
485 Decomposed.StructOffset =
486 adjustToPointerSize(Decomposed.StructOffset, PointerSize);
487 Decomposed.OtherOffset =
488 adjustToPointerSize(Decomposed.OtherOffset, PointerSize);
489 }
Gerolf Hoflehner87ddb652016-01-30 05:52:53 +0000490
Chris Lattner9f7500f2010-08-18 22:07:29 +0000491 // Analyze the base pointer next.
492 V = GEPOp->getOperand(0);
493 } while (--MaxLookup);
Jakub Staszak07f383f2013-08-24 14:16:00 +0000494
Chris Lattner9f7500f2010-08-18 22:07:29 +0000495 // If the chain of expressions is too deep, just return early.
Michael Kuperstein82069c42016-05-25 22:23:08 +0000496 Decomposed.Base = V;
Wei Mid67daae2015-08-05 23:40:30 +0000497 SearchLimitReached++;
Michael Kuperstein82069c42016-05-25 22:23:08 +0000498 return true;
Chris Lattner9f7500f2010-08-18 22:07:29 +0000499}
500
Chandler Carruthc5d81122015-08-06 08:17:06 +0000501/// Returns whether the given pointer value points to memory that is local to
502/// the function, with global constants being considered local to all
503/// functions.
Chandler Carruth7b560d42015-09-09 17:55:00 +0000504bool BasicAAResult::pointsToConstantMemory(const MemoryLocation &Loc,
505 bool OrLocal) {
Dan Gohman9130bad2010-11-08 16:45:26 +0000506 assert(Visited.empty() && "Visited must be cleared after use!");
Chris Lattner2d332972008-06-16 06:30:22 +0000507
Dan Gohman142ff822010-11-08 20:26:19 +0000508 unsigned MaxLookup = 8;
Dan Gohman9130bad2010-11-08 16:45:26 +0000509 SmallVector<const Value *, 16> Worklist;
510 Worklist.push_back(Loc.Ptr);
511 do {
Chandler Carruth7b560d42015-09-09 17:55:00 +0000512 const Value *V = GetUnderlyingObject(Worklist.pop_back_val(), DL);
David Blaikie70573dc2014-11-19 07:49:26 +0000513 if (!Visited.insert(V).second) {
Dan Gohman9130bad2010-11-08 16:45:26 +0000514 Visited.clear();
Chandler Carruth7b560d42015-09-09 17:55:00 +0000515 return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
Dan Gohman9130bad2010-11-08 16:45:26 +0000516 }
Dan Gohman5f1702e2010-08-06 01:25:49 +0000517
Dan Gohman9130bad2010-11-08 16:45:26 +0000518 // An alloca instruction defines local memory.
519 if (OrLocal && isa<AllocaInst>(V))
520 continue;
521
522 // A global constant counts as local memory for our purposes.
523 if (const GlobalVariable *GV = dyn_cast<GlobalVariable>(V)) {
524 // Note: this doesn't require GV to be "ODR" because it isn't legal for a
525 // global to be marked constant in some modules and non-constant in
526 // others. GV may even be a declaration, not a definition.
527 if (!GV->isConstant()) {
528 Visited.clear();
Chandler Carruth7b560d42015-09-09 17:55:00 +0000529 return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
Dan Gohman9130bad2010-11-08 16:45:26 +0000530 }
531 continue;
532 }
533
534 // If both select values point to local memory, then so does the select.
535 if (const SelectInst *SI = dyn_cast<SelectInst>(V)) {
536 Worklist.push_back(SI->getTrueValue());
537 Worklist.push_back(SI->getFalseValue());
538 continue;
539 }
540
541 // If all values incoming to a phi node point to local memory, then so does
542 // the phi.
543 if (const PHINode *PN = dyn_cast<PHINode>(V)) {
Dan Gohman142ff822010-11-08 20:26:19 +0000544 // Don't bother inspecting phi nodes with many operands.
545 if (PN->getNumIncomingValues() > MaxLookup) {
546 Visited.clear();
Chandler Carruth7b560d42015-09-09 17:55:00 +0000547 return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
Dan Gohman142ff822010-11-08 20:26:19 +0000548 }
Pete Cooper833f34d2015-05-12 20:05:31 +0000549 for (Value *IncValue : PN->incoming_values())
550 Worklist.push_back(IncValue);
Dan Gohman9130bad2010-11-08 16:45:26 +0000551 continue;
552 }
553
554 // Otherwise be conservative.
555 Visited.clear();
Chandler Carruth7b560d42015-09-09 17:55:00 +0000556 return AAResultBase::pointsToConstantMemory(Loc, OrLocal);
Dan Gohman9130bad2010-11-08 16:45:26 +0000557
Dan Gohman142ff822010-11-08 20:26:19 +0000558 } while (!Worklist.empty() && --MaxLookup);
Dan Gohman9130bad2010-11-08 16:45:26 +0000559
560 Visited.clear();
Dan Gohman142ff822010-11-08 20:26:19 +0000561 return Worklist.empty();
Chris Lattner2d332972008-06-16 06:30:22 +0000562}
563
Chandler Carruthc5d81122015-08-06 08:17:06 +0000564/// Returns the behavior when calling the given call site.
Chandler Carruth7b560d42015-09-09 17:55:00 +0000565FunctionModRefBehavior BasicAAResult::getModRefBehavior(ImmutableCallSite CS) {
Dan Gohman5f1702e2010-08-06 01:25:49 +0000566 if (CS.doesNotAccessMemory())
567 // Can't do better than this.
Chandler Carruth194f59c2015-07-22 23:15:57 +0000568 return FMRB_DoesNotAccessMemory;
Dan Gohman5f1702e2010-08-06 01:25:49 +0000569
Chandler Carruth194f59c2015-07-22 23:15:57 +0000570 FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior;
Dan Gohman5f1702e2010-08-06 01:25:49 +0000571
572 // If the callsite knows it only reads memory, don't return worse
573 // than that.
574 if (CS.onlyReadsMemory())
Chandler Carruth194f59c2015-07-22 23:15:57 +0000575 Min = FMRB_OnlyReadsMemory;
Nicolai Haehnle84c9f992016-07-04 08:01:29 +0000576 else if (CS.doesNotReadMemory())
577 Min = FMRB_DoesNotReadMemory;
Dan Gohman5f1702e2010-08-06 01:25:49 +0000578
Igor Laevsky39d662f2015-07-11 10:30:36 +0000579 if (CS.onlyAccessesArgMemory())
Chandler Carruth194f59c2015-07-22 23:15:57 +0000580 Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesArgumentPointees);
Igor Laevsky39d662f2015-07-11 10:30:36 +0000581
Chandler Carruth12884f72016-03-02 15:56:53 +0000582 // If CS has operand bundles then aliasing attributes from the function it
583 // calls do not directly apply to the CallSite. This can be made more
584 // precise in the future.
585 if (!CS.hasOperandBundles())
586 if (const Function *F = CS.getCalledFunction())
587 Min =
588 FunctionModRefBehavior(Min & getBestAAResults().getModRefBehavior(F));
589
590 return Min;
Dan Gohman5f1702e2010-08-06 01:25:49 +0000591}
592
Chandler Carruthc5d81122015-08-06 08:17:06 +0000593/// Returns the behavior when calling the given function. For use when the call
594/// site is not known.
Chandler Carruth7b560d42015-09-09 17:55:00 +0000595FunctionModRefBehavior BasicAAResult::getModRefBehavior(const Function *F) {
Dan Gohmane461d7d2010-11-08 16:08:43 +0000596 // If the function declares it doesn't access memory, we can't do better.
Dan Gohman5f1702e2010-08-06 01:25:49 +0000597 if (F->doesNotAccessMemory())
Chandler Carruth194f59c2015-07-22 23:15:57 +0000598 return FMRB_DoesNotAccessMemory;
Dan Gohmane461d7d2010-11-08 16:08:43 +0000599
Chandler Carruth194f59c2015-07-22 23:15:57 +0000600 FunctionModRefBehavior Min = FMRB_UnknownModRefBehavior;
Dan Gohman2694e142010-11-10 01:02:18 +0000601
Dan Gohmane461d7d2010-11-08 16:08:43 +0000602 // If the function declares it only reads memory, go with that.
Dan Gohman5f1702e2010-08-06 01:25:49 +0000603 if (F->onlyReadsMemory())
Chandler Carruth194f59c2015-07-22 23:15:57 +0000604 Min = FMRB_OnlyReadsMemory;
Nicolai Haehnle84c9f992016-07-04 08:01:29 +0000605 else if (F->doesNotReadMemory())
606 Min = FMRB_DoesNotReadMemory;
Dan Gohman5f1702e2010-08-06 01:25:49 +0000607
Igor Laevsky39d662f2015-07-11 10:30:36 +0000608 if (F->onlyAccessesArgMemory())
Chandler Carruth194f59c2015-07-22 23:15:57 +0000609 Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesArgumentPointees);
Andrew Kaylor9604f342016-11-08 21:07:42 +0000610 else if (F->onlyAccessesInaccessibleMemory())
611 Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesInaccessibleMem);
612 else if (F->onlyAccessesInaccessibleMemOrArgMem())
613 Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesInaccessibleOrArgMem);
Igor Laevsky39d662f2015-07-11 10:30:36 +0000614
Chandler Carruth12884f72016-03-02 15:56:53 +0000615 return Min;
Dan Gohman5f1702e2010-08-06 01:25:49 +0000616}
Owen Anderson98a36172009-02-05 23:36:27 +0000617
Nicolai Haehnle84c9f992016-07-04 08:01:29 +0000618/// Returns true if this is a writeonly (i.e Mod only) parameter.
Philip Reamesfe46cad2016-01-06 18:10:35 +0000619static bool isWriteOnlyParam(ImmutableCallSite CS, unsigned ArgIdx,
620 const TargetLibraryInfo &TLI) {
Nicolai Haehnle84c9f992016-07-04 08:01:29 +0000621 if (CS.paramHasAttr(ArgIdx + 1, Attribute::WriteOnly))
622 return true;
Hal Finkel354e23b2014-07-17 01:28:25 +0000623
624 // We can bound the aliasing properties of memset_pattern16 just as we can
625 // for memcpy/memset. This is particularly important because the
626 // LoopIdiomRecognizer likes to turn loops into calls to memset_pattern16
Nicolai Haehnle84c9f992016-07-04 08:01:29 +0000627 // whenever possible.
628 // FIXME Consider handling this in InferFunctionAttr.cpp together with other
629 // attributes.
Ahmed Bougachad765a822016-04-27 19:04:35 +0000630 LibFunc::Func F;
631 if (CS.getCalledFunction() && TLI.getLibFunc(*CS.getCalledFunction(), F) &&
632 F == LibFunc::memset_pattern16 && TLI.has(F))
Philip Reamesae050a52016-01-06 04:53:16 +0000633 if (ArgIdx == 0)
Philip Reamesfe46cad2016-01-06 18:10:35 +0000634 return true;
635
636 // TODO: memset_pattern4, memset_pattern8
637 // TODO: _chk variants
638 // TODO: strcmp, strcpy
639
640 return false;
641}
642
643ModRefInfo BasicAAResult::getArgModRefInfo(ImmutableCallSite CS,
644 unsigned ArgIdx) {
645
Nicolai Haehnle84c9f992016-07-04 08:01:29 +0000646 // Checking for known builtin intrinsics and target library functions.
Philip Reamesfe46cad2016-01-06 18:10:35 +0000647 if (isWriteOnlyParam(CS, ArgIdx, TLI))
648 return MRI_Mod;
Hal Finkel354e23b2014-07-17 01:28:25 +0000649
Igor Laevsky36e84c02015-10-28 16:42:00 +0000650 if (CS.paramHasAttr(ArgIdx + 1, Attribute::ReadOnly))
651 return MRI_Ref;
652
Igor Laevsky559d1702015-10-28 17:54:48 +0000653 if (CS.paramHasAttr(ArgIdx + 1, Attribute::ReadNone))
654 return MRI_NoModRef;
655
Chandler Carruth7b560d42015-09-09 17:55:00 +0000656 return AAResultBase::getArgModRefInfo(CS, ArgIdx);
Hal Finkel354e23b2014-07-17 01:28:25 +0000657}
658
Sanjoy Dasd47f4242016-05-10 02:35:41 +0000659static bool isIntrinsicCall(ImmutableCallSite CS, Intrinsic::ID IID) {
Hal Finkel93046912014-07-25 21:13:35 +0000660 const IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction());
Sanjoy Dasd47f4242016-05-10 02:35:41 +0000661 return II && II->getIntrinsicID() == IID;
Hal Finkel93046912014-07-25 21:13:35 +0000662}
663
Justin Bognerabdcb3c2015-09-24 05:29:31 +0000664#ifndef NDEBUG
Justin Bogner49655f82015-09-24 04:59:24 +0000665static const Function *getParent(const Value *V) {
666 if (const Instruction *inst = dyn_cast<Instruction>(V))
667 return inst->getParent()->getParent();
668
669 if (const Argument *arg = dyn_cast<Argument>(V))
670 return arg->getParent();
671
672 return nullptr;
673}
674
675static bool notDifferentParent(const Value *O1, const Value *O2) {
676
677 const Function *F1 = getParent(O1);
678 const Function *F2 = getParent(O2);
679
680 return !F1 || !F2 || F1 == F2;
681}
Justin Bognerabdcb3c2015-09-24 05:29:31 +0000682#endif
Justin Bogner49655f82015-09-24 04:59:24 +0000683
684AliasResult BasicAAResult::alias(const MemoryLocation &LocA,
685 const MemoryLocation &LocB) {
686 assert(notDifferentParent(LocA.Ptr, LocB.Ptr) &&
687 "BasicAliasAnalysis doesn't support interprocedural queries.");
688
689 // If we have a directly cached entry for these locations, we have recursed
690 // through this once, so just return the cached results. Notably, when this
691 // happens, we don't clear the cache.
692 auto CacheIt = AliasCache.find(LocPair(LocA, LocB));
693 if (CacheIt != AliasCache.end())
694 return CacheIt->second;
695
696 AliasResult Alias = aliasCheck(LocA.Ptr, LocA.Size, LocA.AATags, LocB.Ptr,
697 LocB.Size, LocB.AATags);
698 // AliasCache rarely has more than 1 or 2 elements, always use
699 // shrink_and_clear so it quickly returns to the inline capacity of the
700 // SmallDenseMap if it ever grows larger.
701 // FIXME: This should really be shrink_to_inline_capacity_and_clear().
702 AliasCache.shrink_and_clear();
703 VisitedPhiBBs.clear();
704 return Alias;
705}
706
Chandler Carruthc5d81122015-08-06 08:17:06 +0000707/// Checks to see if the specified callsite can clobber the specified memory
708/// object.
709///
710/// Since we only look at local properties of this function, we really can't
711/// say much about this query. We do, however, use simple "address taken"
712/// analysis on local objects.
Chandler Carruth7b560d42015-09-09 17:55:00 +0000713ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS,
714 const MemoryLocation &Loc) {
Dan Gohman41f14cf2010-09-14 21:25:10 +0000715 assert(notDifferentParent(CS.getInstruction(), Loc.Ptr) &&
Dan Gohman00ef9322010-07-07 14:27:09 +0000716 "AliasAnalysis query involving multiple functions!");
717
Chandler Carruth7b560d42015-09-09 17:55:00 +0000718 const Value *Object = GetUnderlyingObject(Loc.Ptr, DL);
Jakub Staszak07f383f2013-08-24 14:16:00 +0000719
Dan Gohman41f14cf2010-09-14 21:25:10 +0000720 // If this is a tail call and Loc.Ptr points to a stack location, we know that
Chris Lattnerd6a49ad2009-11-22 16:05:05 +0000721 // the tail call cannot access or modify the local stack.
722 // We cannot exclude byval arguments here; these belong to the caller of
723 // the current function not to the current function, and a tail callee
724 // may reference them.
725 if (isa<AllocaInst>(Object))
Dan Gohman5442c712010-08-03 21:48:53 +0000726 if (const CallInst *CI = dyn_cast<CallInst>(CS.getInstruction()))
Chris Lattnerd6a49ad2009-11-22 16:05:05 +0000727 if (CI->isTailCall())
Chandler Carruth194f59c2015-07-22 23:15:57 +0000728 return MRI_NoModRef;
Jakub Staszak07f383f2013-08-24 14:16:00 +0000729
Chris Lattnerd6a49ad2009-11-22 16:05:05 +0000730 // If the pointer is to a locally allocated object that does not escape,
Chris Lattner84ed59ab2009-11-23 16:44:43 +0000731 // then the call can not mod/ref the pointer unless the call takes the pointer
732 // as an argument, and itself doesn't capture it.
Chris Lattner1e7b37e2009-11-23 16:46:41 +0000733 if (!isa<Constant>(Object) && CS.getInstruction() != Object &&
Dan Gohman84f90a32010-07-01 20:08:40 +0000734 isNonEscapingLocalObject(Object)) {
Chris Lattner84ed59ab2009-11-23 16:44:43 +0000735 bool PassedAsArg = false;
Igor Laevsky28eeb3f2016-01-16 12:15:53 +0000736 unsigned OperandNo = 0;
737 for (auto CI = CS.data_operands_begin(), CE = CS.data_operands_end();
738 CI != CE; ++CI, ++OperandNo) {
Chris Lattner026f5e62011-05-23 05:15:43 +0000739 // Only look at the no-capture or byval pointer arguments. If this
740 // pointer were passed to arguments that were neither of these, then it
741 // couldn't be no-capture.
Duncan Sands19d0b472010-02-16 11:11:14 +0000742 if (!(*CI)->getType()->isPointerTy() ||
Hal Finkel39fed392016-12-15 05:09:15 +0000743 (!CS.doesNotCapture(OperandNo) &&
744 OperandNo < CS.getNumArgOperands() && !CS.isByValArgument(OperandNo)))
Chris Lattner84ed59ab2009-11-23 16:44:43 +0000745 continue;
Jakub Staszak07f383f2013-08-24 14:16:00 +0000746
Dan Gohman41f14cf2010-09-14 21:25:10 +0000747 // If this is a no-capture pointer argument, see if we can tell that it
Chris Lattner84ed59ab2009-11-23 16:44:43 +0000748 // is impossible to alias the pointer we're checking. If not, we have to
749 // assume that the call could touch the pointer, even though it doesn't
750 // escape.
Chandler Carruth7b560d42015-09-09 17:55:00 +0000751 AliasResult AR =
752 getBestAAResults().alias(MemoryLocation(*CI), MemoryLocation(Object));
753 if (AR) {
Chris Lattner84ed59ab2009-11-23 16:44:43 +0000754 PassedAsArg = true;
755 break;
756 }
757 }
Jakub Staszak07f383f2013-08-24 14:16:00 +0000758
Chris Lattner84ed59ab2009-11-23 16:44:43 +0000759 if (!PassedAsArg)
Chandler Carruth194f59c2015-07-22 23:15:57 +0000760 return MRI_NoModRef;
Chris Lattnerd6a49ad2009-11-22 16:05:05 +0000761 }
762
Philip Reamesd9f4a3d2016-03-09 23:19:56 +0000763 // If the CallSite is to malloc or calloc, we can assume that it doesn't
764 // modify any IR visible value. This is only valid because we assume these
765 // routines do not read values visible in the IR. TODO: Consider special
766 // casing realloc and strdup routines which access only their arguments as
767 // well. Or alternatively, replace all of this with inaccessiblememonly once
768 // that's implemented fully.
769 auto *Inst = CS.getInstruction();
770 if (isMallocLikeFn(Inst, &TLI) || isCallocLikeFn(Inst, &TLI)) {
771 // Be conservative if the accessed pointer may alias the allocation -
772 // fallback to the generic handling below.
773 if (getBestAAResults().alias(MemoryLocation(Inst), Loc) == NoAlias)
774 return MRI_NoModRef;
775 }
776
Hal Finkel93046912014-07-25 21:13:35 +0000777 // While the assume intrinsic is marked as arbitrarily writing so that
778 // proper control dependencies will be maintained, it never aliases any
779 // particular memory location.
Sanjoy Dasd47f4242016-05-10 02:35:41 +0000780 if (isIntrinsicCall(CS, Intrinsic::assume))
Chandler Carruth194f59c2015-07-22 23:15:57 +0000781 return MRI_NoModRef;
Hal Finkel93046912014-07-25 21:13:35 +0000782
Sanjoy Dasd47f4242016-05-10 02:35:41 +0000783 // Like assumes, guard intrinsics are also marked as arbitrarily writing so
784 // that proper control dependencies are maintained but they never mods any
785 // particular memory location.
786 //
787 // *Unlike* assumes, guard intrinsics are modeled as reading memory since the
788 // heap state at the point the guard is issued needs to be consistent in case
789 // the guard invokes the "deopt" continuation.
790 if (isIntrinsicCall(CS, Intrinsic::experimental_guard))
791 return MRI_Ref;
792
Anna Thomas037e5402016-08-09 17:18:05 +0000793 // Like assumes, invariant.start intrinsics were also marked as arbitrarily
794 // writing so that proper control dependencies are maintained but they never
795 // mod any particular memory location visible to the IR.
796 // *Unlike* assumes (which are now modeled as NoModRef), invariant.start
797 // intrinsic is now modeled as reading memory. This prevents hoisting the
798 // invariant.start intrinsic over stores. Consider:
799 // *ptr = 40;
800 // *ptr = 50;
801 // invariant_start(ptr)
802 // int val = *ptr;
803 // print(val);
804 //
805 // This cannot be transformed to:
806 //
807 // *ptr = 40;
808 // invariant_start(ptr)
809 // *ptr = 50;
810 // int val = *ptr;
811 // print(val);
812 //
813 // The transformation will cause the second store to be ignored (based on
814 // rules of invariant.start) and print 40, while the first program always
815 // prints 50.
816 if (isIntrinsicCall(CS, Intrinsic::invariant_start))
817 return MRI_Ref;
818
Chandler Carruth7b560d42015-09-09 17:55:00 +0000819 // The AAResultBase base class has some smarts, lets use them.
820 return AAResultBase::getModRefInfo(CS, Loc);
Dan Gohman64d842e2010-09-08 01:32:20 +0000821}
Chris Lattner2d332972008-06-16 06:30:22 +0000822
Chandler Carruth7b560d42015-09-09 17:55:00 +0000823ModRefInfo BasicAAResult::getModRefInfo(ImmutableCallSite CS1,
824 ImmutableCallSite CS2) {
Hal Finkel93046912014-07-25 21:13:35 +0000825 // While the assume intrinsic is marked as arbitrarily writing so that
826 // proper control dependencies will be maintained, it never aliases any
827 // particular memory location.
Sanjoy Dasd47f4242016-05-10 02:35:41 +0000828 if (isIntrinsicCall(CS1, Intrinsic::assume) ||
829 isIntrinsicCall(CS2, Intrinsic::assume))
Chandler Carruth194f59c2015-07-22 23:15:57 +0000830 return MRI_NoModRef;
Hal Finkel93046912014-07-25 21:13:35 +0000831
Sanjoy Dasd47f4242016-05-10 02:35:41 +0000832 // Like assumes, guard intrinsics are also marked as arbitrarily writing so
833 // that proper control dependencies are maintained but they never mod any
834 // particular memory location.
835 //
836 // *Unlike* assumes, guard intrinsics are modeled as reading memory since the
837 // heap state at the point the guard is issued needs to be consistent in case
838 // the guard invokes the "deopt" continuation.
839
840 // NB! This function is *not* commutative, so we specical case two
841 // possibilities for guard intrinsics.
842
843 if (isIntrinsicCall(CS1, Intrinsic::experimental_guard))
844 return getModRefBehavior(CS2) & MRI_Mod ? MRI_Ref : MRI_NoModRef;
845
846 if (isIntrinsicCall(CS2, Intrinsic::experimental_guard))
847 return getModRefBehavior(CS1) & MRI_Mod ? MRI_Mod : MRI_NoModRef;
848
Chandler Carruth7b560d42015-09-09 17:55:00 +0000849 // The AAResultBase base class has some smarts, lets use them.
850 return AAResultBase::getModRefInfo(CS1, CS2);
Hal Finkel93046912014-07-25 21:13:35 +0000851}
852
Chandler Carruthc5d81122015-08-06 08:17:06 +0000853/// Provide ad-hoc rules to disambiguate accesses through two GEP operators,
854/// both having the exact same pointer operand.
Chandler Carruthc3f49eb2015-06-22 02:16:51 +0000855static AliasResult aliasSameBasePointerGEPs(const GEPOperator *GEP1,
856 uint64_t V1Size,
857 const GEPOperator *GEP2,
858 uint64_t V2Size,
859 const DataLayout &DL) {
Ahmed Bougacha29efe3b2015-02-07 17:04:29 +0000860
Hal Finkel5c12d8f2016-07-11 01:32:20 +0000861 assert(GEP1->getPointerOperand()->stripPointerCasts() ==
862 GEP2->getPointerOperand()->stripPointerCasts() &&
863 GEP1->getPointerOperand()->getType() ==
864 GEP2->getPointerOperand()->getType() &&
Ahmed Bougacha29efe3b2015-02-07 17:04:29 +0000865 "Expected GEPs with the same pointer operand");
866
867 // Try to determine whether GEP1 and GEP2 index through arrays, into structs,
868 // such that the struct field accesses provably cannot alias.
869 // We also need at least two indices (the pointer, and the struct field).
Daniel Berlin73694bb2016-06-01 18:55:32 +0000870 if (GEP1->getNumIndices() != GEP2->getNumIndices() ||
871 GEP1->getNumIndices() < 2)
Chandler Carruthc3f49eb2015-06-22 02:16:51 +0000872 return MayAlias;
Ahmed Bougacha29efe3b2015-02-07 17:04:29 +0000873
874 // If we don't know the size of the accesses through both GEPs, we can't
875 // determine whether the struct fields accessed can't alias.
Chandler Carruthecbd1682015-06-17 07:21:38 +0000876 if (V1Size == MemoryLocation::UnknownSize ||
877 V2Size == MemoryLocation::UnknownSize)
Chandler Carruthc3f49eb2015-06-22 02:16:51 +0000878 return MayAlias;
Ahmed Bougacha29efe3b2015-02-07 17:04:29 +0000879
880 ConstantInt *C1 =
881 dyn_cast<ConstantInt>(GEP1->getOperand(GEP1->getNumOperands() - 1));
882 ConstantInt *C2 =
883 dyn_cast<ConstantInt>(GEP2->getOperand(GEP2->getNumOperands() - 1));
884
James Molloy5a4d8cd2015-10-22 13:28:18 +0000885 // If the last (struct) indices are constants and are equal, the other indices
886 // might be also be dynamically equal, so the GEPs can alias.
Vedant Kumaree202942016-05-11 15:45:43 +0000887 if (C1 && C2 && C1->getSExtValue() == C2->getSExtValue())
Chandler Carruthc3f49eb2015-06-22 02:16:51 +0000888 return MayAlias;
Ahmed Bougacha29efe3b2015-02-07 17:04:29 +0000889
890 // Find the last-indexed type of the GEP, i.e., the type you'd get if
891 // you stripped the last index.
892 // On the way, look at each indexed type. If there's something other
893 // than an array, different indices can lead to different final types.
894 SmallVector<Value *, 8> IntermediateIndices;
895
896 // Insert the first index; we don't need to check the type indexed
897 // through it as it only drops the pointer indirection.
898 assert(GEP1->getNumIndices() > 1 && "Not enough GEP indices to examine");
899 IntermediateIndices.push_back(GEP1->getOperand(1));
900
901 // Insert all the remaining indices but the last one.
902 // Also, check that they all index through arrays.
903 for (unsigned i = 1, e = GEP1->getNumIndices() - 1; i != e; ++i) {
904 if (!isa<ArrayType>(GetElementPtrInst::getIndexedType(
David Blaikied288fb82015-03-30 21:41:43 +0000905 GEP1->getSourceElementType(), IntermediateIndices)))
Chandler Carruthc3f49eb2015-06-22 02:16:51 +0000906 return MayAlias;
Ahmed Bougacha29efe3b2015-02-07 17:04:29 +0000907 IntermediateIndices.push_back(GEP1->getOperand(i + 1));
908 }
909
James Molloy5a4d8cd2015-10-22 13:28:18 +0000910 auto *Ty = GetElementPtrInst::getIndexedType(
911 GEP1->getSourceElementType(), IntermediateIndices);
912 StructType *LastIndexedStruct = dyn_cast<StructType>(Ty);
Ahmed Bougacha29efe3b2015-02-07 17:04:29 +0000913
James Molloy5a4d8cd2015-10-22 13:28:18 +0000914 if (isa<SequentialType>(Ty)) {
915 // We know that:
916 // - both GEPs begin indexing from the exact same pointer;
917 // - the last indices in both GEPs are constants, indexing into a sequential
918 // type (array or pointer);
919 // - both GEPs only index through arrays prior to that.
920 //
921 // Because array indices greater than the number of elements are valid in
922 // GEPs, unless we know the intermediate indices are identical between
923 // GEP1 and GEP2 we cannot guarantee that the last indexed arrays don't
James Molloy05a896a2015-10-23 14:17:03 +0000924 // partially overlap. We also need to check that the loaded size matches
925 // the element size, otherwise we could still have overlap.
926 const uint64_t ElementSize =
927 DL.getTypeStoreSize(cast<SequentialType>(Ty)->getElementType());
928 if (V1Size != ElementSize || V2Size != ElementSize)
929 return MayAlias;
930
James Molloy5a4d8cd2015-10-22 13:28:18 +0000931 for (unsigned i = 0, e = GEP1->getNumIndices() - 1; i != e; ++i)
932 if (GEP1->getOperand(i + 1) != GEP2->getOperand(i + 1))
933 return MayAlias;
James Molloy05a896a2015-10-23 14:17:03 +0000934
James Molloy5a4d8cd2015-10-22 13:28:18 +0000935 // Now we know that the array/pointer that GEP1 indexes into and that
936 // that GEP2 indexes into must either precisely overlap or be disjoint.
937 // Because they cannot partially overlap and because fields in an array
938 // cannot overlap, if we can prove the final indices are different between
939 // GEP1 and GEP2, we can conclude GEP1 and GEP2 don't alias.
940
941 // If the last indices are constants, we've already checked they don't
942 // equal each other so we can exit early.
943 if (C1 && C2)
944 return NoAlias;
945 if (isKnownNonEqual(GEP1->getOperand(GEP1->getNumOperands() - 1),
946 GEP2->getOperand(GEP2->getNumOperands() - 1),
947 DL))
948 return NoAlias;
Chandler Carruthc3f49eb2015-06-22 02:16:51 +0000949 return MayAlias;
James Molloy5a4d8cd2015-10-22 13:28:18 +0000950 } else if (!LastIndexedStruct || !C1 || !C2) {
951 return MayAlias;
952 }
Ahmed Bougacha29efe3b2015-02-07 17:04:29 +0000953
954 // We know that:
955 // - both GEPs begin indexing from the exact same pointer;
956 // - the last indices in both GEPs are constants, indexing into a struct;
957 // - said indices are different, hence, the pointed-to fields are different;
958 // - both GEPs only index through arrays prior to that.
959 //
960 // This lets us determine that the struct that GEP1 indexes into and the
961 // struct that GEP2 indexes into must either precisely overlap or be
962 // completely disjoint. Because they cannot partially overlap, indexing into
963 // different non-overlapping fields of the struct will never alias.
964
965 // Therefore, the only remaining thing needed to show that both GEPs can't
966 // alias is that the fields are not overlapping.
967 const StructLayout *SL = DL.getStructLayout(LastIndexedStruct);
968 const uint64_t StructSize = SL->getSizeInBytes();
969 const uint64_t V1Off = SL->getElementOffset(C1->getZExtValue());
970 const uint64_t V2Off = SL->getElementOffset(C2->getZExtValue());
971
972 auto EltsDontOverlap = [StructSize](uint64_t V1Off, uint64_t V1Size,
973 uint64_t V2Off, uint64_t V2Size) {
974 return V1Off < V2Off && V1Off + V1Size <= V2Off &&
975 ((V2Off + V2Size <= StructSize) ||
976 (V2Off + V2Size - StructSize <= V1Off));
977 };
978
979 if (EltsDontOverlap(V1Off, V1Size, V2Off, V2Size) ||
980 EltsDontOverlap(V2Off, V2Size, V1Off, V1Size))
Chandler Carruthc3f49eb2015-06-22 02:16:51 +0000981 return NoAlias;
Ahmed Bougacha29efe3b2015-02-07 17:04:29 +0000982
Chandler Carruthc3f49eb2015-06-22 02:16:51 +0000983 return MayAlias;
Ahmed Bougacha29efe3b2015-02-07 17:04:29 +0000984}
985
Michael Kuperstein82069c42016-05-25 22:23:08 +0000986// If a we have (a) a GEP and (b) a pointer based on an alloca, and the
987// beginning of the object the GEP points would have a negative offset with
988// repsect to the alloca, that means the GEP can not alias pointer (b).
989// Note that the pointer based on the alloca may not be a GEP. For
990// example, it may be the alloca itself.
Michael Kupersteinae214912016-05-26 19:30:49 +0000991// The same applies if (b) is based on a GlobalVariable. Note that just being
992// based on isIdentifiedObject() is not enough - we need an identified object
993// that does not permit access to negative offsets. For example, a negative
994// offset from a noalias argument or call can be inbounds w.r.t the actual
995// underlying object.
Michael Kuperstein82069c42016-05-25 22:23:08 +0000996//
997// For example, consider:
998//
999// struct { int f0, int f1, ...} foo;
1000// foo alloca;
1001// foo* random = bar(alloca);
1002// int *f0 = &alloca.f0
1003// int *f1 = &random->f1;
1004//
1005// Which is lowered, approximately, to:
1006//
1007// %alloca = alloca %struct.foo
1008// %random = call %struct.foo* @random(%struct.foo* %alloca)
1009// %f0 = getelementptr inbounds %struct, %struct.foo* %alloca, i32 0, i32 0
1010// %f1 = getelementptr inbounds %struct, %struct.foo* %random, i32 0, i32 1
1011//
1012// Assume %f1 and %f0 alias. Then %f1 would point into the object allocated
1013// by %alloca. Since the %f1 GEP is inbounds, that means %random must also
1014// point into the same object. But since %f0 points to the beginning of %alloca,
1015// the highest %f1 can be is (%alloca + 3). This means %random can not be higher
1016// than (%alloca - 1), and so is not inbounds, a contradiction.
1017bool BasicAAResult::isGEPBaseAtNegativeOffset(const GEPOperator *GEPOp,
Michael Kupersteinae214912016-05-26 19:30:49 +00001018 const DecomposedGEP &DecompGEP, const DecomposedGEP &DecompObject,
1019 uint64_t ObjectAccessSize) {
1020 // If the object access size is unknown, or the GEP isn't inbounds, bail.
1021 if (ObjectAccessSize == MemoryLocation::UnknownSize || !GEPOp->isInBounds())
Michael Kuperstein82069c42016-05-25 22:23:08 +00001022 return false;
1023
Michael Kupersteinae214912016-05-26 19:30:49 +00001024 // We need the object to be an alloca or a globalvariable, and want to know
1025 // the offset of the pointer from the object precisely, so no variable
1026 // indices are allowed.
1027 if (!(isa<AllocaInst>(DecompObject.Base) ||
1028 isa<GlobalVariable>(DecompObject.Base)) ||
1029 !DecompObject.VarIndices.empty())
Michael Kuperstein82069c42016-05-25 22:23:08 +00001030 return false;
1031
Michael Kupersteinae214912016-05-26 19:30:49 +00001032 int64_t ObjectBaseOffset = DecompObject.StructOffset +
1033 DecompObject.OtherOffset;
Michael Kuperstein82069c42016-05-25 22:23:08 +00001034
1035 // If the GEP has no variable indices, we know the precise offset
1036 // from the base, then use it. If the GEP has variable indices, we're in
1037 // a bit more trouble: we can't count on the constant offsets that come
1038 // from non-struct sources, since these can be "rewound" by a negative
1039 // variable offset. So use only offsets that came from structs.
1040 int64_t GEPBaseOffset = DecompGEP.StructOffset;
1041 if (DecompGEP.VarIndices.empty())
1042 GEPBaseOffset += DecompGEP.OtherOffset;
1043
Michael Kupersteinae214912016-05-26 19:30:49 +00001044 return (GEPBaseOffset >= ObjectBaseOffset + (int64_t)ObjectAccessSize);
Michael Kuperstein82069c42016-05-25 22:23:08 +00001045}
1046
Chandler Carruthc5d81122015-08-06 08:17:06 +00001047/// Provides a bunch of ad-hoc rules to disambiguate a GEP instruction against
1048/// another pointer.
Chris Lattnera99edbe2009-11-26 02:11:08 +00001049///
Chandler Carruthc5d81122015-08-06 08:17:06 +00001050/// We know that V1 is a GEP, but we don't know anything about V2.
1051/// UnderlyingV1 is GetUnderlyingObject(GEP1, DL), UnderlyingV2 is the same for
1052/// V2.
Chandler Carruth7b560d42015-09-09 17:55:00 +00001053AliasResult BasicAAResult::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size,
1054 const AAMDNodes &V1AAInfo, const Value *V2,
1055 uint64_t V2Size, const AAMDNodes &V2AAInfo,
1056 const Value *UnderlyingV1,
1057 const Value *UnderlyingV2) {
Michael Kuperstein82069c42016-05-25 22:23:08 +00001058 DecomposedGEP DecompGEP1, DecompGEP2;
1059 bool GEP1MaxLookupReached =
Hal Finkel3ca4a6b2016-12-15 03:02:15 +00001060 DecomposeGEPExpression(GEP1, DecompGEP1, DL, DT);
Michael Kuperstein82069c42016-05-25 22:23:08 +00001061 bool GEP2MaxLookupReached =
Hal Finkel3ca4a6b2016-12-15 03:02:15 +00001062 DecomposeGEPExpression(V2, DecompGEP2, DL, DT);
Chris Lattner7a5b56a2009-11-26 02:17:34 +00001063
Michael Kuperstein82069c42016-05-25 22:23:08 +00001064 int64_t GEP1BaseOffset = DecompGEP1.StructOffset + DecompGEP1.OtherOffset;
1065 int64_t GEP2BaseOffset = DecompGEP2.StructOffset + DecompGEP2.OtherOffset;
1066
1067 assert(DecompGEP1.Base == UnderlyingV1 && DecompGEP2.Base == UnderlyingV2 &&
1068 "DecomposeGEPExpression returned a result different from "
1069 "GetUnderlyingObject");
1070
1071 // If the GEP's offset relative to its base is such that the base would
1072 // fall below the start of the object underlying V2, then the GEP and V2
1073 // cannot alias.
1074 if (!GEP1MaxLookupReached && !GEP2MaxLookupReached &&
1075 isGEPBaseAtNegativeOffset(GEP1, DecompGEP1, DecompGEP2, V2Size))
1076 return NoAlias;
Arnold Schwaighofer76dca582012-09-06 14:31:51 +00001077 // If we have two gep instructions with must-alias or not-alias'ing base
1078 // pointers, figure out if the indexes to the GEP tell us anything about the
1079 // derived pointer.
Chris Lattnera99edbe2009-11-26 02:11:08 +00001080 if (const GEPOperator *GEP2 = dyn_cast<GEPOperator>(V2)) {
Michael Kuperstein82069c42016-05-25 22:23:08 +00001081 // Check for the GEP base being at a negative offset, this time in the other
1082 // direction.
1083 if (!GEP1MaxLookupReached && !GEP2MaxLookupReached &&
1084 isGEPBaseAtNegativeOffset(GEP2, DecompGEP2, DecompGEP1, V1Size))
1085 return NoAlias;
Arnold Schwaighoferaadf1042013-03-26 18:07:53 +00001086 // Do the base pointers alias?
Chandler Carruthecbd1682015-06-17 07:21:38 +00001087 AliasResult BaseAlias =
1088 aliasCheck(UnderlyingV1, MemoryLocation::UnknownSize, AAMDNodes(),
1089 UnderlyingV2, MemoryLocation::UnknownSize, AAMDNodes());
Arnold Schwaighoferaadf1042013-03-26 18:07:53 +00001090
Arnold Schwaighofer76dca582012-09-06 14:31:51 +00001091 // Check for geps of non-aliasing underlying pointers where the offsets are
1092 // identical.
Arnold Schwaighoferaadf1042013-03-26 18:07:53 +00001093 if ((BaseAlias == MayAlias) && V1Size == V2Size) {
Arnold Schwaighofer76dca582012-09-06 14:31:51 +00001094 // Do the base pointers alias assuming type and size.
Chandler Carruth903c5f92015-08-06 07:57:58 +00001095 AliasResult PreciseBaseAlias = aliasCheck(UnderlyingV1, V1Size, V1AAInfo,
1096 UnderlyingV2, V2Size, V2AAInfo);
Arnold Schwaighofer76dca582012-09-06 14:31:51 +00001097 if (PreciseBaseAlias == NoAlias) {
1098 // See if the computed offset from the common pointer tells us about the
1099 // relation of the resulting pointer.
Arnold Schwaighofer1a444482014-03-26 21:30:19 +00001100 // If the max search depth is reached the result is undefined
1101 if (GEP2MaxLookupReached || GEP1MaxLookupReached)
1102 return MayAlias;
1103
Arnold Schwaighofer76dca582012-09-06 14:31:51 +00001104 // Same offsets.
1105 if (GEP1BaseOffset == GEP2BaseOffset &&
Michael Kuperstein82069c42016-05-25 22:23:08 +00001106 DecompGEP1.VarIndices == DecompGEP2.VarIndices)
Arnold Schwaighofer76dca582012-09-06 14:31:51 +00001107 return NoAlias;
Arnold Schwaighofer76dca582012-09-06 14:31:51 +00001108 }
1109 }
Jakub Staszak07f383f2013-08-24 14:16:00 +00001110
Chris Lattner7a5b56a2009-11-26 02:17:34 +00001111 // If we get a No or May, then return it immediately, no amount of analysis
1112 // will improve this situation.
Chandler Carruth903c5f92015-08-06 07:57:58 +00001113 if (BaseAlias != MustAlias)
1114 return BaseAlias;
Jakub Staszak07f383f2013-08-24 14:16:00 +00001115
Chris Lattner7a5b56a2009-11-26 02:17:34 +00001116 // Otherwise, we have a MustAlias. Since the base pointers alias each other
1117 // exactly, see if the computed offset from the common pointer tells us
1118 // about the relation of the resulting pointer.
Ahmed Bougacha29efe3b2015-02-07 17:04:29 +00001119 // If we know the two GEPs are based off of the exact same pointer (and not
1120 // just the same underlying object), see if that tells us anything about
1121 // the resulting pointers.
Hal Finkel5c12d8f2016-07-11 01:32:20 +00001122 if (GEP1->getPointerOperand()->stripPointerCasts() ==
1123 GEP2->getPointerOperand()->stripPointerCasts() &&
1124 GEP1->getPointerOperand()->getType() ==
1125 GEP2->getPointerOperand()->getType()) {
Chandler Carruth7b560d42015-09-09 17:55:00 +00001126 AliasResult R = aliasSameBasePointerGEPs(GEP1, V1Size, GEP2, V2Size, DL);
Ahmed Bougacha29efe3b2015-02-07 17:04:29 +00001127 // If we couldn't find anything interesting, don't abandon just yet.
1128 if (R != MayAlias)
1129 return R;
1130 }
1131
Sanjay Patel9613b292016-01-17 23:13:48 +00001132 // If the max search depth is reached, the result is undefined
Arnold Schwaighofer1a444482014-03-26 21:30:19 +00001133 if (GEP2MaxLookupReached || GEP1MaxLookupReached)
1134 return MayAlias;
Jakub Staszak07f383f2013-08-24 14:16:00 +00001135
Chris Lattner7a5b56a2009-11-26 02:17:34 +00001136 // Subtract the GEP2 pointer from the GEP1 pointer to find out their
1137 // symbolic difference.
1138 GEP1BaseOffset -= GEP2BaseOffset;
Michael Kuperstein82069c42016-05-25 22:23:08 +00001139 GetIndexDifference(DecompGEP1.VarIndices, DecompGEP2.VarIndices);
Jakub Staszak07f383f2013-08-24 14:16:00 +00001140
Chris Lattner7a5b56a2009-11-26 02:17:34 +00001141 } else {
1142 // Check to see if these two pointers are related by the getelementptr
1143 // instruction. If one pointer is a GEP with a non-zero index of the other
1144 // pointer, we know they cannot alias.
Chris Lattner5c1cfc22009-11-26 16:52:32 +00001145
1146 // If both accesses are unknown size, we can't do anything useful here.
Chandler Carruthecbd1682015-06-17 07:21:38 +00001147 if (V1Size == MemoryLocation::UnknownSize &&
1148 V2Size == MemoryLocation::UnknownSize)
Chris Lattner7a5b56a2009-11-26 02:17:34 +00001149 return MayAlias;
Chris Lattner6ea17f77f2003-12-11 22:44:13 +00001150
Chandler Carruthecbd1682015-06-17 07:21:38 +00001151 AliasResult R = aliasCheck(UnderlyingV1, MemoryLocation::UnknownSize,
Ehsan Amiri17e17012016-08-12 16:05:03 +00001152 AAMDNodes(), V2, V2Size, V2AAInfo,
1153 nullptr, UnderlyingV2);
Chris Lattner7a5b56a2009-11-26 02:17:34 +00001154 if (R != MustAlias)
1155 // If V2 may alias GEP base pointer, conservatively returns MayAlias.
1156 // If V2 is known not to alias GEP base pointer, then the two values
1157 // cannot alias per GEP semantics: "A pointer value formed from a
1158 // getelementptr instruction is associated with the addresses associated
1159 // with the first operand of the getelementptr".
1160 return R;
Chris Lattner6ea17f77f2003-12-11 22:44:13 +00001161
Arnold Schwaighofer1a444482014-03-26 21:30:19 +00001162 // If the max search depth is reached the result is undefined
1163 if (GEP1MaxLookupReached)
1164 return MayAlias;
Chris Lattner6ea17f77f2003-12-11 22:44:13 +00001165 }
Jakub Staszak07f383f2013-08-24 14:16:00 +00001166
Chris Lattner7a5b56a2009-11-26 02:17:34 +00001167 // In the two GEP Case, if there is no difference in the offsets of the
1168 // computed pointers, the resultant pointers are a must alias. This
Sanjay Patel9613b292016-01-17 23:13:48 +00001169 // happens when we have two lexically identical GEP's (for example).
Chris Lattnerd6a2a992003-02-26 19:41:54 +00001170 //
Chris Lattner7a5b56a2009-11-26 02:17:34 +00001171 // In the other case, if we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2
1172 // must aliases the GEP, the end result is a must alias also.
Michael Kuperstein82069c42016-05-25 22:23:08 +00001173 if (GEP1BaseOffset == 0 && DecompGEP1.VarIndices.empty())
Evan Chengc1eed9d2009-10-14 06:41:49 +00001174 return MustAlias;
Evan Chengf1f3dd32009-10-13 18:42:04 +00001175
Eli Friedman3d1b3072011-09-08 02:23:31 +00001176 // If there is a constant difference between the pointers, but the difference
1177 // is less than the size of the associated memory object, then we know
1178 // that the objects are partially overlapping. If the difference is
1179 // greater, we know they do not overlap.
Michael Kuperstein82069c42016-05-25 22:23:08 +00001180 if (GEP1BaseOffset != 0 && DecompGEP1.VarIndices.empty()) {
Eli Friedman3d1b3072011-09-08 02:23:31 +00001181 if (GEP1BaseOffset >= 0) {
Chandler Carruthecbd1682015-06-17 07:21:38 +00001182 if (V2Size != MemoryLocation::UnknownSize) {
Eli Friedman3d1b3072011-09-08 02:23:31 +00001183 if ((uint64_t)GEP1BaseOffset < V2Size)
1184 return PartialAlias;
1185 return NoAlias;
1186 }
1187 } else {
Arnold Schwaighofere3ac0992014-01-16 04:53:18 +00001188 // We have the situation where:
1189 // + +
1190 // | BaseOffset |
1191 // ---------------->|
1192 // |-->V1Size |-------> V2Size
1193 // GEP1 V2
1194 // We need to know that V2Size is not unknown, otherwise we might have
1195 // stripped a gep with negative index ('gep <ptr>, -1, ...).
Chandler Carruthecbd1682015-06-17 07:21:38 +00001196 if (V1Size != MemoryLocation::UnknownSize &&
1197 V2Size != MemoryLocation::UnknownSize) {
Eli Friedman3d1b3072011-09-08 02:23:31 +00001198 if (-(uint64_t)GEP1BaseOffset < V1Size)
1199 return PartialAlias;
1200 return NoAlias;
1201 }
1202 }
Dan Gohmanc4bf5ca2010-12-13 22:50:24 +00001203 }
1204
Michael Kuperstein82069c42016-05-25 22:23:08 +00001205 if (!DecompGEP1.VarIndices.empty()) {
Eli Friedmanb78ac542011-09-08 02:37:07 +00001206 uint64_t Modulo = 0;
Quentin Colombet5989bc62015-08-31 22:32:47 +00001207 bool AllPositive = true;
Michael Kuperstein82069c42016-05-25 22:23:08 +00001208 for (unsigned i = 0, e = DecompGEP1.VarIndices.size(); i != e; ++i) {
Quentin Colombet5989bc62015-08-31 22:32:47 +00001209
1210 // Try to distinguish something like &A[i][1] against &A[42][0].
1211 // Grab the least significant bit set in any of the scales. We
1212 // don't need std::abs here (even if the scale's negative) as we'll
1213 // be ^'ing Modulo with itself later.
Michael Kuperstein82069c42016-05-25 22:23:08 +00001214 Modulo |= (uint64_t)DecompGEP1.VarIndices[i].Scale;
Quentin Colombet5989bc62015-08-31 22:32:47 +00001215
1216 if (AllPositive) {
1217 // If the Value could change between cycles, then any reasoning about
1218 // the Value this cycle may not hold in the next cycle. We'll just
1219 // give up if we can't determine conditions that hold for every cycle:
Michael Kuperstein82069c42016-05-25 22:23:08 +00001220 const Value *V = DecompGEP1.VarIndices[i].V;
Quentin Colombet5989bc62015-08-31 22:32:47 +00001221
1222 bool SignKnownZero, SignKnownOne;
Chandler Carruth7b560d42015-09-09 17:55:00 +00001223 ComputeSignBit(const_cast<Value *>(V), SignKnownZero, SignKnownOne, DL,
Hal Finkel3ca4a6b2016-12-15 03:02:15 +00001224 0, nullptr, DT);
Quentin Colombet5989bc62015-08-31 22:32:47 +00001225
1226 // Zero-extension widens the variable, and so forces the sign
1227 // bit to zero.
Michael Kuperstein82069c42016-05-25 22:23:08 +00001228 bool IsZExt = DecompGEP1.VarIndices[i].ZExtBits > 0 || isa<ZExtInst>(V);
Quentin Colombet5989bc62015-08-31 22:32:47 +00001229 SignKnownZero |= IsZExt;
1230 SignKnownOne &= !IsZExt;
1231
1232 // If the variable begins with a zero then we know it's
1233 // positive, regardless of whether the value is signed or
1234 // unsigned.
Michael Kuperstein82069c42016-05-25 22:23:08 +00001235 int64_t Scale = DecompGEP1.VarIndices[i].Scale;
Quentin Colombet5989bc62015-08-31 22:32:47 +00001236 AllPositive =
1237 (SignKnownZero && Scale >= 0) || (SignKnownOne && Scale < 0);
1238 }
1239 }
1240
Eli Friedmanb78ac542011-09-08 02:37:07 +00001241 Modulo = Modulo ^ (Modulo & (Modulo - 1));
Eli Friedman3d1b3072011-09-08 02:23:31 +00001242
Eli Friedmanb78ac542011-09-08 02:37:07 +00001243 // We can compute the difference between the two addresses
1244 // mod Modulo. Check whether that difference guarantees that the
1245 // two locations do not alias.
1246 uint64_t ModOffset = (uint64_t)GEP1BaseOffset & (Modulo - 1);
Chandler Carruthecbd1682015-06-17 07:21:38 +00001247 if (V1Size != MemoryLocation::UnknownSize &&
1248 V2Size != MemoryLocation::UnknownSize && ModOffset >= V2Size &&
1249 V1Size <= Modulo - ModOffset)
Eli Friedmanb78ac542011-09-08 02:37:07 +00001250 return NoAlias;
Quentin Colombet5989bc62015-08-31 22:32:47 +00001251
1252 // If we know all the variables are positive, then GEP1 >= GEP1BasePtr.
1253 // If GEP1BasePtr > V2 (GEP1BaseOffset > 0) then we know the pointers
1254 // don't alias if V2Size can fit in the gap between V2 and GEP1BasePtr.
1255 if (AllPositive && GEP1BaseOffset > 0 && V2Size <= (uint64_t)GEP1BaseOffset)
1256 return NoAlias;
1257
Michael Kuperstein82069c42016-05-25 22:23:08 +00001258 if (constantOffsetHeuristic(DecompGEP1.VarIndices, V1Size, V2Size,
Hal Finkel3ca4a6b2016-12-15 03:02:15 +00001259 GEP1BaseOffset, DT))
Quentin Colombet5989bc62015-08-31 22:32:47 +00001260 return NoAlias;
Eli Friedmanb78ac542011-09-08 02:37:07 +00001261 }
Eli Friedman3d1b3072011-09-08 02:23:31 +00001262
Dan Gohmanadf80ae2011-06-04 06:50:18 +00001263 // Statically, we can see that the base objects are the same, but the
1264 // pointers have dynamic offsets which we can't resolve. And none of our
1265 // little tricks above worked.
1266 //
1267 // TODO: Returning PartialAlias instead of MayAlias is a mild hack; the
1268 // practical effect of this is protecting TBAA in the case of dynamic
Dan Gohman9017b842012-02-17 18:33:38 +00001269 // indices into arrays of unions or malloc'd memory.
Dan Gohmanadf80ae2011-06-04 06:50:18 +00001270 return PartialAlias;
Evan Chengf1f3dd32009-10-13 18:42:04 +00001271}
1272
Chandler Carruthc3f49eb2015-06-22 02:16:51 +00001273static AliasResult MergeAliasResults(AliasResult A, AliasResult B) {
Dan Gohman4e7e7952011-06-03 20:17:36 +00001274 // If the results agree, take it.
1275 if (A == B)
1276 return A;
1277 // A mix of PartialAlias and MustAlias is PartialAlias.
Chandler Carruthc3f49eb2015-06-22 02:16:51 +00001278 if ((A == PartialAlias && B == MustAlias) ||
1279 (B == PartialAlias && A == MustAlias))
1280 return PartialAlias;
Dan Gohman4e7e7952011-06-03 20:17:36 +00001281 // Otherwise, we don't know anything.
Chandler Carruthc3f49eb2015-06-22 02:16:51 +00001282 return MayAlias;
Dan Gohman4e7e7952011-06-03 20:17:36 +00001283}
1284
Chandler Carruthc5d81122015-08-06 08:17:06 +00001285/// Provides a bunch of ad-hoc rules to disambiguate a Select instruction
1286/// against another.
Chandler Carruth7b560d42015-09-09 17:55:00 +00001287AliasResult BasicAAResult::aliasSelect(const SelectInst *SI, uint64_t SISize,
1288 const AAMDNodes &SIAAInfo,
1289 const Value *V2, uint64_t V2Size,
Ehsan Amiri17e17012016-08-12 16:05:03 +00001290 const AAMDNodes &V2AAInfo,
1291 const Value *UnderV2) {
Dan Gohman3b7ba5f2009-10-26 21:55:43 +00001292 // If the values are Selects with the same condition, we can do a more precise
1293 // check: just check for aliases between the values on corresponding arms.
1294 if (const SelectInst *SI2 = dyn_cast<SelectInst>(V2))
1295 if (SI->getCondition() == SI2->getCondition()) {
Chandler Carruth903c5f92015-08-06 07:57:58 +00001296 AliasResult Alias = aliasCheck(SI->getTrueValue(), SISize, SIAAInfo,
1297 SI2->getTrueValue(), V2Size, V2AAInfo);
Dan Gohman3b7ba5f2009-10-26 21:55:43 +00001298 if (Alias == MayAlias)
1299 return MayAlias;
1300 AliasResult ThisAlias =
Chandler Carruth903c5f92015-08-06 07:57:58 +00001301 aliasCheck(SI->getFalseValue(), SISize, SIAAInfo,
1302 SI2->getFalseValue(), V2Size, V2AAInfo);
Dan Gohman4e7e7952011-06-03 20:17:36 +00001303 return MergeAliasResults(ThisAlias, Alias);
Dan Gohman3b7ba5f2009-10-26 21:55:43 +00001304 }
1305
1306 // If both arms of the Select node NoAlias or MustAlias V2, then returns
1307 // NoAlias / MustAlias. Otherwise, returns MayAlias.
1308 AliasResult Alias =
Ehsan Amiri17e17012016-08-12 16:05:03 +00001309 aliasCheck(V2, V2Size, V2AAInfo, SI->getTrueValue(),
1310 SISize, SIAAInfo, UnderV2);
Dan Gohman3b7ba5f2009-10-26 21:55:43 +00001311 if (Alias == MayAlias)
1312 return MayAlias;
Dan Gohman7c34ece2010-06-28 21:16:52 +00001313
Dan Gohman3b7ba5f2009-10-26 21:55:43 +00001314 AliasResult ThisAlias =
Ehsan Amiri17e17012016-08-12 16:05:03 +00001315 aliasCheck(V2, V2Size, V2AAInfo, SI->getFalseValue(), SISize, SIAAInfo,
1316 UnderV2);
Dan Gohman4e7e7952011-06-03 20:17:36 +00001317 return MergeAliasResults(ThisAlias, Alias);
Dan Gohman3b7ba5f2009-10-26 21:55:43 +00001318}
1319
Chandler Carruthc5d81122015-08-06 08:17:06 +00001320/// Provide a bunch of ad-hoc rules to disambiguate a PHI instruction against
1321/// another.
Chandler Carruth7b560d42015-09-09 17:55:00 +00001322AliasResult BasicAAResult::aliasPHI(const PHINode *PN, uint64_t PNSize,
1323 const AAMDNodes &PNAAInfo, const Value *V2,
Ehsan Amiri17e17012016-08-12 16:05:03 +00001324 uint64_t V2Size, const AAMDNodes &V2AAInfo,
1325 const Value *UnderV2) {
Arnold Schwaighofer0d10a9d2014-01-02 03:31:36 +00001326 // Track phi nodes we have visited. We use this information when we determine
1327 // value equivalence.
1328 VisitedPhiBBs.insert(PN->getParent());
1329
Dan Gohman3b7ba5f2009-10-26 21:55:43 +00001330 // If the values are PHIs in the same block, we can do a more precise
1331 // as well as efficient check: just check for aliases between the values
1332 // on corresponding edges.
1333 if (const PHINode *PN2 = dyn_cast<PHINode>(V2))
1334 if (PN2->getParent() == PN->getParent()) {
Chandler Carruthac80dc72015-06-17 07:18:54 +00001335 LocPair Locs(MemoryLocation(PN, PNSize, PNAAInfo),
1336 MemoryLocation(V2, V2Size, V2AAInfo));
Arnold Schwaighofer8dc34cf2012-09-06 14:41:53 +00001337 if (PN > V2)
1338 std::swap(Locs.first, Locs.second);
Arnold Schwaighoferedd62b12012-12-10 23:02:41 +00001339 // Analyse the PHIs' inputs under the assumption that the PHIs are
1340 // NoAlias.
1341 // If the PHIs are May/MustAlias there must be (recursively) an input
1342 // operand from outside the PHIs' cycle that is MayAlias/MustAlias or
1343 // there must be an operation on the PHIs within the PHIs' value cycle
1344 // that causes a MayAlias.
1345 // Pretend the phis do not alias.
1346 AliasResult Alias = NoAlias;
1347 assert(AliasCache.count(Locs) &&
1348 "There must exist an entry for the phi node");
1349 AliasResult OrigAliasResult = AliasCache[Locs];
1350 AliasCache[Locs] = NoAlias;
Arnold Schwaighofer8dc34cf2012-09-06 14:41:53 +00001351
Hal Finkela6f86fc2012-11-17 02:33:15 +00001352 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
Dan Gohman3b7ba5f2009-10-26 21:55:43 +00001353 AliasResult ThisAlias =
Chandler Carruth903c5f92015-08-06 07:57:58 +00001354 aliasCheck(PN->getIncomingValue(i), PNSize, PNAAInfo,
1355 PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)),
1356 V2Size, V2AAInfo);
Dan Gohman4e7e7952011-06-03 20:17:36 +00001357 Alias = MergeAliasResults(ThisAlias, Alias);
1358 if (Alias == MayAlias)
1359 break;
Dan Gohman3b7ba5f2009-10-26 21:55:43 +00001360 }
Arnold Schwaighofer8dc34cf2012-09-06 14:41:53 +00001361
1362 // Reset if speculation failed.
Arnold Schwaighoferedd62b12012-12-10 23:02:41 +00001363 if (Alias != NoAlias)
Arnold Schwaighofer8dc34cf2012-09-06 14:41:53 +00001364 AliasCache[Locs] = OrigAliasResult;
1365
Dan Gohman3b7ba5f2009-10-26 21:55:43 +00001366 return Alias;
1367 }
1368
Chandler Carruth903c5f92015-08-06 07:57:58 +00001369 SmallPtrSet<Value *, 4> UniqueSrc;
1370 SmallVector<Value *, 4> V1Srcs;
Tobias Edler von Kochd8ce16b2015-07-15 19:32:22 +00001371 bool isRecursive = false;
Pete Cooper833f34d2015-05-12 20:05:31 +00001372 for (Value *PV1 : PN->incoming_values()) {
Evan Chengc10e88d2009-10-13 22:02:20 +00001373 if (isa<PHINode>(PV1))
1374 // If any of the source itself is a PHI, return MayAlias conservatively
Evan Chengc1eed9d2009-10-14 06:41:49 +00001375 // to avoid compile time explosion. The worst possible case is if both
1376 // sides are PHI nodes. In which case, this is O(m x n) time where 'm'
1377 // and 'n' are the number of PHI sources.
Evan Chengc10e88d2009-10-13 22:02:20 +00001378 return MayAlias;
Tobias Edler von Kochd8ce16b2015-07-15 19:32:22 +00001379
1380 if (EnableRecPhiAnalysis)
1381 if (GEPOperator *PV1GEP = dyn_cast<GEPOperator>(PV1)) {
1382 // Check whether the incoming value is a GEP that advances the pointer
1383 // result of this PHI node (e.g. in a loop). If this is the case, we
1384 // would recurse and always get a MayAlias. Handle this case specially
1385 // below.
1386 if (PV1GEP->getPointerOperand() == PN && PV1GEP->getNumIndices() == 1 &&
1387 isa<ConstantInt>(PV1GEP->idx_begin())) {
1388 isRecursive = true;
1389 continue;
1390 }
1391 }
1392
David Blaikie70573dc2014-11-19 07:49:26 +00001393 if (UniqueSrc.insert(PV1).second)
Evan Chengc10e88d2009-10-13 22:02:20 +00001394 V1Srcs.push_back(PV1);
1395 }
1396
Tobias Edler von Kochd8ce16b2015-07-15 19:32:22 +00001397 // If this PHI node is recursive, set the size of the accessed memory to
1398 // unknown to represent all the possible values the GEP could advance the
1399 // pointer to.
1400 if (isRecursive)
1401 PNSize = MemoryLocation::UnknownSize;
1402
Chandler Carruth903c5f92015-08-06 07:57:58 +00001403 AliasResult Alias =
Ehsan Amiri17e17012016-08-12 16:05:03 +00001404 aliasCheck(V2, V2Size, V2AAInfo, V1Srcs[0],
1405 PNSize, PNAAInfo, UnderV2);
Tobias Edler von Kochd8ce16b2015-07-15 19:32:22 +00001406
Evan Chengf92f5552009-10-14 05:22:03 +00001407 // Early exit if the check of the first PHI source against V2 is MayAlias.
1408 // Other results are not possible.
1409 if (Alias == MayAlias)
1410 return MayAlias;
1411
Evan Chengc10e88d2009-10-13 22:02:20 +00001412 // If all sources of the PHI node NoAlias or MustAlias V2, then returns
1413 // NoAlias / MustAlias. Otherwise, returns MayAlias.
Evan Chengc10e88d2009-10-13 22:02:20 +00001414 for (unsigned i = 1, e = V1Srcs.size(); i != e; ++i) {
1415 Value *V = V1Srcs[i];
Dan Gohman3b7ba5f2009-10-26 21:55:43 +00001416
Chandler Carruth903c5f92015-08-06 07:57:58 +00001417 AliasResult ThisAlias =
Ehsan Amiri17e17012016-08-12 16:05:03 +00001418 aliasCheck(V2, V2Size, V2AAInfo, V, PNSize, PNAAInfo, UnderV2);
Dan Gohman4e7e7952011-06-03 20:17:36 +00001419 Alias = MergeAliasResults(ThisAlias, Alias);
1420 if (Alias == MayAlias)
1421 break;
Evan Chengc10e88d2009-10-13 22:02:20 +00001422 }
1423
1424 return Alias;
1425}
1426
David Majnemer0345b0f2015-11-17 08:15:08 +00001427/// Provides a bunch of ad-hoc rules to disambiguate in common cases, such as
Chandler Carruthc5d81122015-08-06 08:17:06 +00001428/// array references.
Chandler Carruth7b560d42015-09-09 17:55:00 +00001429AliasResult BasicAAResult::aliasCheck(const Value *V1, uint64_t V1Size,
1430 AAMDNodes V1AAInfo, const Value *V2,
Ehsan Amiri17e17012016-08-12 16:05:03 +00001431 uint64_t V2Size, AAMDNodes V2AAInfo,
1432 const Value *O1, const Value *O2) {
Dan Gohmancb45bd92010-04-08 18:11:50 +00001433 // If either of the memory references is empty, it doesn't matter what the
1434 // pointer values are.
1435 if (V1Size == 0 || V2Size == 0)
1436 return NoAlias;
1437
Evan Chengf1f3dd32009-10-13 18:42:04 +00001438 // Strip off any casts if they exist.
1439 V1 = V1->stripPointerCasts();
1440 V2 = V2->stripPointerCasts();
1441
Daniel Berlin3459d6e2015-05-05 18:10:49 +00001442 // If V1 or V2 is undef, the result is NoAlias because we can always pick a
1443 // value for undef that aliases nothing in the program.
1444 if (isa<UndefValue>(V1) || isa<UndefValue>(V2))
1445 return NoAlias;
1446
Evan Chengf1f3dd32009-10-13 18:42:04 +00001447 // Are we checking for alias of the same value?
Sanjay Patel9613b292016-01-17 23:13:48 +00001448 // Because we look 'through' phi nodes, we could look at "Value" pointers from
Arnold Schwaighofer833a82e2014-01-03 05:47:03 +00001449 // different iterations. We must therefore make sure that this is not the
1450 // case. The function isValueEqualInPotentialCycles ensures that this cannot
1451 // happen by looking at the visited phi nodes and making sure they cannot
1452 // reach the value.
1453 if (isValueEqualInPotentialCycles(V1, V2))
1454 return MustAlias;
Evan Chengf1f3dd32009-10-13 18:42:04 +00001455
Duncan Sands19d0b472010-02-16 11:11:14 +00001456 if (!V1->getType()->isPointerTy() || !V2->getType()->isPointerTy())
Chandler Carruth903c5f92015-08-06 07:57:58 +00001457 return NoAlias; // Scalars cannot alias each other
Evan Chengf1f3dd32009-10-13 18:42:04 +00001458
1459 // Figure out what objects these things are pointing to if we can.
Ehsan Amiri17e17012016-08-12 16:05:03 +00001460 if (O1 == nullptr)
1461 O1 = GetUnderlyingObject(V1, DL, MaxLookupSearchDepth);
1462
1463 if (O2 == nullptr)
1464 O2 = GetUnderlyingObject(V2, DL, MaxLookupSearchDepth);
Evan Chengf1f3dd32009-10-13 18:42:04 +00001465
Dan Gohmanccb45842009-11-09 19:29:11 +00001466 // Null values in the default address space don't point to any object, so they
1467 // don't alias any other pointer.
1468 if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O1))
1469 if (CPN->getType()->getAddressSpace() == 0)
1470 return NoAlias;
1471 if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O2))
1472 if (CPN->getType()->getAddressSpace() == 0)
1473 return NoAlias;
1474
Evan Chengf1f3dd32009-10-13 18:42:04 +00001475 if (O1 != O2) {
Sanjay Patel9613b292016-01-17 23:13:48 +00001476 // If V1/V2 point to two different objects, we know that we have no alias.
Dan Gohman00ef9322010-07-07 14:27:09 +00001477 if (isIdentifiedObject(O1) && isIdentifiedObject(O2))
Evan Chengf1f3dd32009-10-13 18:42:04 +00001478 return NoAlias;
Nick Lewyckyc53e2ec2009-11-14 06:15:14 +00001479
1480 // Constant pointers can't alias with non-const isIdentifiedObject objects.
Dan Gohman00ef9322010-07-07 14:27:09 +00001481 if ((isa<Constant>(O1) && isIdentifiedObject(O2) && !isa<Constant>(O2)) ||
1482 (isa<Constant>(O2) && isIdentifiedObject(O1) && !isa<Constant>(O1)))
Nick Lewyckyc53e2ec2009-11-14 06:15:14 +00001483 return NoAlias;
1484
Michael Kupersteinf3e663a2013-05-28 08:17:48 +00001485 // Function arguments can't alias with things that are known to be
1486 // unambigously identified at the function level.
1487 if ((isa<Argument>(O1) && isIdentifiedFunctionLocal(O2)) ||
1488 (isa<Argument>(O2) && isIdentifiedFunctionLocal(O1)))
Dan Gohman84f90a32010-07-01 20:08:40 +00001489 return NoAlias;
Evan Chengf1f3dd32009-10-13 18:42:04 +00001490
1491 // Most objects can't alias null.
Dan Gohman00ef9322010-07-07 14:27:09 +00001492 if ((isa<ConstantPointerNull>(O2) && isKnownNonNull(O1)) ||
1493 (isa<ConstantPointerNull>(O1) && isKnownNonNull(O2)))
Evan Chengf1f3dd32009-10-13 18:42:04 +00001494 return NoAlias;
Jakub Staszak07f383f2013-08-24 14:16:00 +00001495
Dan Gohman5b0a8a82010-07-07 14:30:04 +00001496 // If one pointer is the result of a call/invoke or load and the other is a
1497 // non-escaping local object within the same function, then we know the
1498 // object couldn't escape to a point where the call could return it.
1499 //
1500 // Note that if the pointers are in different functions, there are a
1501 // variety of complications. A call with a nocapture argument may still
1502 // temporary store the nocapture argument's value in a temporary memory
1503 // location if that memory location doesn't escape. Or it may pass a
1504 // nocapture value to other functions as long as they don't capture it.
1505 if (isEscapeSource(O1) && isNonEscapingLocalObject(O2))
1506 return NoAlias;
1507 if (isEscapeSource(O2) && isNonEscapingLocalObject(O1))
1508 return NoAlias;
1509 }
1510
Evan Chengf1f3dd32009-10-13 18:42:04 +00001511 // If the size of one access is larger than the entire object on the other
1512 // side, then we know such behavior is undefined and can assume no alias.
Chandler Carruth7b560d42015-09-09 17:55:00 +00001513 if ((V1Size != MemoryLocation::UnknownSize &&
1514 isObjectSmallerThan(O2, V1Size, DL, TLI)) ||
1515 (V2Size != MemoryLocation::UnknownSize &&
1516 isObjectSmallerThan(O1, V2Size, DL, TLI)))
1517 return NoAlias;
Jakub Staszak07f383f2013-08-24 14:16:00 +00001518
Dan Gohmanfb02cec2011-06-04 00:31:50 +00001519 // Check the cache before climbing up use-def chains. This also terminates
1520 // otherwise infinitely recursive queries.
Chandler Carruthac80dc72015-06-17 07:18:54 +00001521 LocPair Locs(MemoryLocation(V1, V1Size, V1AAInfo),
1522 MemoryLocation(V2, V2Size, V2AAInfo));
Dan Gohmanfb02cec2011-06-04 00:31:50 +00001523 if (V1 > V2)
1524 std::swap(Locs.first, Locs.second);
1525 std::pair<AliasCacheTy::iterator, bool> Pair =
Chandler Carruth903c5f92015-08-06 07:57:58 +00001526 AliasCache.insert(std::make_pair(Locs, MayAlias));
Dan Gohmanfb02cec2011-06-04 00:31:50 +00001527 if (!Pair.second)
1528 return Pair.first->second;
1529
Chris Lattner89288992009-11-26 02:13:03 +00001530 // FIXME: This isn't aggressively handling alias(GEP, PHI) for example: if the
1531 // GEP can't simplify, we don't even look at the PHI cases.
Chris Lattnerb2647b92009-10-17 23:48:54 +00001532 if (!isa<GEPOperator>(V1) && isa<GEPOperator>(V2)) {
Chris Lattnerd6a2a992003-02-26 19:41:54 +00001533 std::swap(V1, V2);
1534 std::swap(V1Size, V2Size);
Chris Lattner5341c962009-11-26 02:14:59 +00001535 std::swap(O1, O2);
Hal Finkelcc39b672014-07-24 12:16:19 +00001536 std::swap(V1AAInfo, V2AAInfo);
Chris Lattnerd6a2a992003-02-26 19:41:54 +00001537 }
Dan Gohman02538ac2010-10-18 18:04:47 +00001538 if (const GEPOperator *GV1 = dyn_cast<GEPOperator>(V1)) {
Chandler Carruth903c5f92015-08-06 07:57:58 +00001539 AliasResult Result =
1540 aliasGEP(GV1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, O1, O2);
1541 if (Result != MayAlias)
1542 return AliasCache[Locs] = Result;
Dan Gohman02538ac2010-10-18 18:04:47 +00001543 }
Evan Chengc10e88d2009-10-13 22:02:20 +00001544
1545 if (isa<PHINode>(V2) && !isa<PHINode>(V1)) {
1546 std::swap(V1, V2);
Ehsan Amiri17e17012016-08-12 16:05:03 +00001547 std::swap(O1, O2);
Evan Chengc10e88d2009-10-13 22:02:20 +00001548 std::swap(V1Size, V2Size);
Hal Finkelcc39b672014-07-24 12:16:19 +00001549 std::swap(V1AAInfo, V2AAInfo);
Evan Chengc10e88d2009-10-13 22:02:20 +00001550 }
Dan Gohman02538ac2010-10-18 18:04:47 +00001551 if (const PHINode *PN = dyn_cast<PHINode>(V1)) {
Ehsan Amiri17e17012016-08-12 16:05:03 +00001552 AliasResult Result = aliasPHI(PN, V1Size, V1AAInfo,
1553 V2, V2Size, V2AAInfo, O2);
Chandler Carruth903c5f92015-08-06 07:57:58 +00001554 if (Result != MayAlias)
1555 return AliasCache[Locs] = Result;
Dan Gohman02538ac2010-10-18 18:04:47 +00001556 }
Misha Brukman01808ca2005-04-21 21:13:18 +00001557
Dan Gohman3b7ba5f2009-10-26 21:55:43 +00001558 if (isa<SelectInst>(V2) && !isa<SelectInst>(V1)) {
1559 std::swap(V1, V2);
Ehsan Amiri17e17012016-08-12 16:05:03 +00001560 std::swap(O1, O2);
Dan Gohman3b7ba5f2009-10-26 21:55:43 +00001561 std::swap(V1Size, V2Size);
Hal Finkelcc39b672014-07-24 12:16:19 +00001562 std::swap(V1AAInfo, V2AAInfo);
Dan Gohman3b7ba5f2009-10-26 21:55:43 +00001563 }
Dan Gohman02538ac2010-10-18 18:04:47 +00001564 if (const SelectInst *S1 = dyn_cast<SelectInst>(V1)) {
Chandler Carruth903c5f92015-08-06 07:57:58 +00001565 AliasResult Result =
Ehsan Amiri17e17012016-08-12 16:05:03 +00001566 aliasSelect(S1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, O2);
Chandler Carruth903c5f92015-08-06 07:57:58 +00001567 if (Result != MayAlias)
1568 return AliasCache[Locs] = Result;
Dan Gohman02538ac2010-10-18 18:04:47 +00001569 }
Dan Gohman3b7ba5f2009-10-26 21:55:43 +00001570
Dan Gohman44da55b2011-01-18 21:16:06 +00001571 // If both pointers are pointing into the same object and one of them
Sanjay Patel9613b292016-01-17 23:13:48 +00001572 // accesses the entire object, then the accesses must overlap in some way.
Chandler Carruth7b560d42015-09-09 17:55:00 +00001573 if (O1 == O2)
Chandler Carruthecbd1682015-06-17 07:21:38 +00001574 if ((V1Size != MemoryLocation::UnknownSize &&
Chandler Carruth7b560d42015-09-09 17:55:00 +00001575 isObjectSize(O1, V1Size, DL, TLI)) ||
Chandler Carruthecbd1682015-06-17 07:21:38 +00001576 (V2Size != MemoryLocation::UnknownSize &&
Chandler Carruth7b560d42015-09-09 17:55:00 +00001577 isObjectSize(O2, V2Size, DL, TLI)))
Dan Gohmanfb02cec2011-06-04 00:31:50 +00001578 return AliasCache[Locs] = PartialAlias;
Dan Gohman44da55b2011-01-18 21:16:06 +00001579
Chandler Carruth7b560d42015-09-09 17:55:00 +00001580 // Recurse back into the best AA results we have, potentially with refined
1581 // memory locations. We have already ensured that BasicAA has a MayAlias
1582 // cache result for these, so any recursion back into BasicAA won't loop.
1583 AliasResult Result = getBestAAResults().alias(Locs.first, Locs.second);
Dan Gohmanfb02cec2011-06-04 00:31:50 +00001584 return AliasCache[Locs] = Result;
Chris Lattnerd6a2a992003-02-26 19:41:54 +00001585}
Arnold Schwaighofer0d10a9d2014-01-02 03:31:36 +00001586
Chandler Carruthc5d81122015-08-06 08:17:06 +00001587/// Check whether two Values can be considered equivalent.
1588///
1589/// In addition to pointer equivalence of \p V1 and \p V2 this checks whether
1590/// they can not be part of a cycle in the value graph by looking at all
1591/// visited phi nodes an making sure that the phis cannot reach the value. We
1592/// have to do this because we are looking through phi nodes (That is we say
1593/// noalias(V, phi(VA, VB)) if noalias(V, VA) and noalias(V, VB).
Chandler Carruth7b560d42015-09-09 17:55:00 +00001594bool BasicAAResult::isValueEqualInPotentialCycles(const Value *V,
1595 const Value *V2) {
Arnold Schwaighofer0d10a9d2014-01-02 03:31:36 +00001596 if (V != V2)
1597 return false;
1598
1599 const Instruction *Inst = dyn_cast<Instruction>(V);
1600 if (!Inst)
1601 return true;
1602
Daniel Berlin9e77de22015-03-20 18:05:49 +00001603 if (VisitedPhiBBs.empty())
1604 return true;
1605
Arnold Schwaighofer833a82e2014-01-03 05:47:03 +00001606 if (VisitedPhiBBs.size() > MaxNumPhiBBsValueReachabilityCheck)
1607 return false;
1608
Arnold Schwaighofer833a82e2014-01-03 05:47:03 +00001609 // Make sure that the visited phis cannot reach the Value. This ensures that
1610 // the Values cannot come from different iterations of a potential cycle the
1611 // phi nodes could be involved in.
Craig Topper46276792014-08-24 23:23:06 +00001612 for (auto *P : VisitedPhiBBs)
Duncan P. N. Exon Smith5a82c912015-10-10 00:53:03 +00001613 if (isPotentiallyReachable(&P->front(), Inst, DT, LI))
Arnold Schwaighofer0d10a9d2014-01-02 03:31:36 +00001614 return false;
1615
Arnold Schwaighofer833a82e2014-01-03 05:47:03 +00001616 return true;
Arnold Schwaighofer0d10a9d2014-01-02 03:31:36 +00001617}
1618
Chandler Carruthc5d81122015-08-06 08:17:06 +00001619/// Computes the symbolic difference between two de-composed GEPs.
1620///
1621/// Dest and Src are the variable indices from two decomposed GetElementPtr
1622/// instructions GEP1 and GEP2 which have common base pointers.
Chandler Carruth7b560d42015-09-09 17:55:00 +00001623void BasicAAResult::GetIndexDifference(
Arnold Schwaighofer0d10a9d2014-01-02 03:31:36 +00001624 SmallVectorImpl<VariableGEPIndex> &Dest,
1625 const SmallVectorImpl<VariableGEPIndex> &Src) {
1626 if (Src.empty())
1627 return;
1628
1629 for (unsigned i = 0, e = Src.size(); i != e; ++i) {
1630 const Value *V = Src[i].V;
Quentin Colombet5989bc62015-08-31 22:32:47 +00001631 unsigned ZExtBits = Src[i].ZExtBits, SExtBits = Src[i].SExtBits;
Arnold Schwaighofer0d10a9d2014-01-02 03:31:36 +00001632 int64_t Scale = Src[i].Scale;
1633
1634 // Find V in Dest. This is N^2, but pointer indices almost never have more
1635 // than a few variable indexes.
1636 for (unsigned j = 0, e = Dest.size(); j != e; ++j) {
Arnold Schwaighofer833a82e2014-01-03 05:47:03 +00001637 if (!isValueEqualInPotentialCycles(Dest[j].V, V) ||
Quentin Colombet5989bc62015-08-31 22:32:47 +00001638 Dest[j].ZExtBits != ZExtBits || Dest[j].SExtBits != SExtBits)
Arnold Schwaighofer0d10a9d2014-01-02 03:31:36 +00001639 continue;
1640
1641 // If we found it, subtract off Scale V's from the entry in Dest. If it
1642 // goes to zero, remove the entry.
1643 if (Dest[j].Scale != Scale)
1644 Dest[j].Scale -= Scale;
1645 else
1646 Dest.erase(Dest.begin() + j);
1647 Scale = 0;
1648 break;
1649 }
1650
1651 // If we didn't consume this entry, add it to the end of the Dest list.
1652 if (Scale) {
Quentin Colombet5989bc62015-08-31 22:32:47 +00001653 VariableGEPIndex Entry = {V, ZExtBits, SExtBits, -Scale};
Arnold Schwaighofer0d10a9d2014-01-02 03:31:36 +00001654 Dest.push_back(Entry);
1655 }
1656 }
1657}
Quentin Colombet5989bc62015-08-31 22:32:47 +00001658
Chandler Carruth7b560d42015-09-09 17:55:00 +00001659bool BasicAAResult::constantOffsetHeuristic(
Quentin Colombet5989bc62015-08-31 22:32:47 +00001660 const SmallVectorImpl<VariableGEPIndex> &VarIndices, uint64_t V1Size,
Hal Finkel3ca4a6b2016-12-15 03:02:15 +00001661 uint64_t V2Size, int64_t BaseOffset,
Chandler Carruth7b560d42015-09-09 17:55:00 +00001662 DominatorTree *DT) {
Quentin Colombet5989bc62015-08-31 22:32:47 +00001663 if (VarIndices.size() != 2 || V1Size == MemoryLocation::UnknownSize ||
Chandler Carruth7b560d42015-09-09 17:55:00 +00001664 V2Size == MemoryLocation::UnknownSize)
Quentin Colombet5989bc62015-08-31 22:32:47 +00001665 return false;
1666
1667 const VariableGEPIndex &Var0 = VarIndices[0], &Var1 = VarIndices[1];
1668
1669 if (Var0.ZExtBits != Var1.ZExtBits || Var0.SExtBits != Var1.SExtBits ||
1670 Var0.Scale != -Var1.Scale)
1671 return false;
1672
1673 unsigned Width = Var1.V->getType()->getIntegerBitWidth();
1674
1675 // We'll strip off the Extensions of Var0 and Var1 and do another round
1676 // of GetLinearExpression decomposition. In the example above, if Var0
1677 // is zext(%x + 1) we should get V1 == %x and V1Offset == 1.
1678
1679 APInt V0Scale(Width, 0), V0Offset(Width, 0), V1Scale(Width, 0),
1680 V1Offset(Width, 0);
1681 bool NSW = true, NUW = true;
1682 unsigned V0ZExtBits = 0, V0SExtBits = 0, V1ZExtBits = 0, V1SExtBits = 0;
1683 const Value *V0 = GetLinearExpression(Var0.V, V0Scale, V0Offset, V0ZExtBits,
Hal Finkel3ca4a6b2016-12-15 03:02:15 +00001684 V0SExtBits, DL, 0, DT, NSW, NUW);
Richard Trieu7a083812016-02-18 22:09:30 +00001685 NSW = true;
1686 NUW = true;
Quentin Colombet5989bc62015-08-31 22:32:47 +00001687 const Value *V1 = GetLinearExpression(Var1.V, V1Scale, V1Offset, V1ZExtBits,
Hal Finkel3ca4a6b2016-12-15 03:02:15 +00001688 V1SExtBits, DL, 0, DT, NSW, NUW);
Quentin Colombet5989bc62015-08-31 22:32:47 +00001689
1690 if (V0Scale != V1Scale || V0ZExtBits != V1ZExtBits ||
1691 V0SExtBits != V1SExtBits || !isValueEqualInPotentialCycles(V0, V1))
1692 return false;
1693
1694 // We have a hit - Var0 and Var1 only differ by a constant offset!
1695
1696 // If we've been sext'ed then zext'd the maximum difference between Var0 and
1697 // Var1 is possible to calculate, but we're just interested in the absolute
Benjamin Kramer557b6012015-10-24 11:38:01 +00001698 // minimum difference between the two. The minimum distance may occur due to
Quentin Colombet5989bc62015-08-31 22:32:47 +00001699 // wrapping; consider "add i3 %i, 5": if %i == 7 then 7 + 5 mod 8 == 4, and so
1700 // the minimum distance between %i and %i + 5 is 3.
Benjamin Kramer557b6012015-10-24 11:38:01 +00001701 APInt MinDiff = V0Offset - V1Offset, Wrapped = -MinDiff;
Quentin Colombet5989bc62015-08-31 22:32:47 +00001702 MinDiff = APIntOps::umin(MinDiff, Wrapped);
1703 uint64_t MinDiffBytes = MinDiff.getZExtValue() * std::abs(Var0.Scale);
1704
1705 // We can't definitely say whether GEP1 is before or after V2 due to wrapping
1706 // arithmetic (i.e. for some values of GEP1 and V2 GEP1 < V2, and for other
1707 // values GEP1 > V2). We'll therefore only declare NoAlias if both V1Size and
1708 // V2Size can fit in the MinDiffBytes gap.
1709 return V1Size + std::abs(BaseOffset) <= MinDiffBytes &&
1710 V2Size + std::abs(BaseOffset) <= MinDiffBytes;
1711}
Chandler Carruth7b560d42015-09-09 17:55:00 +00001712
1713//===----------------------------------------------------------------------===//
1714// BasicAliasAnalysis Pass
1715//===----------------------------------------------------------------------===//
1716
Chandler Carruthdab4eae2016-11-23 17:53:26 +00001717AnalysisKey BasicAA::Key;
Chandler Carruthb4faf132016-03-11 10:22:49 +00001718
Sean Silva36e0d012016-08-09 00:28:15 +00001719BasicAAResult BasicAA::run(Function &F, FunctionAnalysisManager &AM) {
Chandler Carruth7b560d42015-09-09 17:55:00 +00001720 return BasicAAResult(F.getParent()->getDataLayout(),
Chandler Carruthb47f8012016-03-11 11:05:24 +00001721 AM.getResult<TargetLibraryAnalysis>(F),
Chandler Carruth5bfbc3f2016-03-11 13:53:18 +00001722 &AM.getResult<DominatorTreeAnalysis>(F),
Chandler Carruthb47f8012016-03-11 11:05:24 +00001723 AM.getCachedResult<LoopAnalysis>(F));
Chandler Carruth7b560d42015-09-09 17:55:00 +00001724}
1725
Keno Fischer277bfae2015-10-26 21:22:58 +00001726BasicAAWrapperPass::BasicAAWrapperPass() : FunctionPass(ID) {
1727 initializeBasicAAWrapperPassPass(*PassRegistry::getPassRegistry());
1728}
1729
Chandler Carruth7b560d42015-09-09 17:55:00 +00001730char BasicAAWrapperPass::ID = 0;
1731void BasicAAWrapperPass::anchor() {}
1732
1733INITIALIZE_PASS_BEGIN(BasicAAWrapperPass, "basicaa",
1734 "Basic Alias Analysis (stateless AA impl)", true, true)
Chandler Carruth5bfbc3f2016-03-11 13:53:18 +00001735INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
Chandler Carruth7b560d42015-09-09 17:55:00 +00001736INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
1737INITIALIZE_PASS_END(BasicAAWrapperPass, "basicaa",
1738 "Basic Alias Analysis (stateless AA impl)", true, true)
1739
1740FunctionPass *llvm::createBasicAAWrapperPass() {
1741 return new BasicAAWrapperPass();
1742}
1743
1744bool BasicAAWrapperPass::runOnFunction(Function &F) {
Chandler Carruth7b560d42015-09-09 17:55:00 +00001745 auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>();
Chandler Carruth5bfbc3f2016-03-11 13:53:18 +00001746 auto &DTWP = getAnalysis<DominatorTreeWrapperPass>();
Chandler Carruth7b560d42015-09-09 17:55:00 +00001747 auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>();
1748
1749 Result.reset(new BasicAAResult(F.getParent()->getDataLayout(), TLIWP.getTLI(),
Hal Finkel3ca4a6b2016-12-15 03:02:15 +00001750 &DTWP.getDomTree(),
Chandler Carruth7b560d42015-09-09 17:55:00 +00001751 LIWP ? &LIWP->getLoopInfo() : nullptr));
1752
1753 return false;
1754}
1755
1756void BasicAAWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
1757 AU.setPreservesAll();
Chandler Carruth5bfbc3f2016-03-11 13:53:18 +00001758 AU.addRequired<DominatorTreeWrapperPass>();
Chandler Carruth7b560d42015-09-09 17:55:00 +00001759 AU.addRequired<TargetLibraryInfoWrapperPass>();
1760}
1761
1762BasicAAResult llvm::createLegacyPMBasicAAResult(Pass &P, Function &F) {
1763 return BasicAAResult(
1764 F.getParent()->getDataLayout(),
Hal Finkel3ca4a6b2016-12-15 03:02:15 +00001765 P.getAnalysis<TargetLibraryInfoWrapperPass>().getTLI());
Chandler Carruth7b560d42015-09-09 17:55:00 +00001766}