blob: d64c658f84369b7d45ee257fd5048ad41fc53b87 [file] [log] [blame]
Owen Andersonef9a6fd2008-04-09 08:23:16 +00001//===- MemCpyOptimizer.cpp - Optimize use of memcpy and friends -----------===//
2//
3// The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This pass performs various transformations related to eliminating memcpy
11// calls, or transforming sets of stores into memset's.
12//
13//===----------------------------------------------------------------------===//
14
Sean Silva6347df02016-06-14 02:44:55 +000015#include "llvm/Transforms/Scalar/MemCpyOptimizer.h"
Owen Andersonef9a6fd2008-04-09 08:23:16 +000016#include "llvm/Transforms/Scalar.h"
Amaury Sechetbdb261b2016-03-14 22:52:27 +000017#include "llvm/ADT/DenseSet.h"
Owen Andersonef9a6fd2008-04-09 08:23:16 +000018#include "llvm/ADT/SmallVector.h"
19#include "llvm/ADT/Statistic.h"
Chris Lattner9cb10352010-12-26 20:15:01 +000020#include "llvm/Analysis/ValueTracking.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000021#include "llvm/IR/DataLayout.h"
Chandler Carruth03eb0de2014-03-04 10:40:04 +000022#include "llvm/IR/GetElementPtrTypeIterator.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000023#include "llvm/IR/GlobalVariable.h"
24#include "llvm/IR/IRBuilder.h"
Owen Andersonef9a6fd2008-04-09 08:23:16 +000025#include "llvm/Support/Debug.h"
Chris Lattnerb25de3f2009-08-23 04:37:46 +000026#include "llvm/Support/raw_ostream.h"
Chandler Carruthaafe0912012-06-29 12:38:19 +000027#include "llvm/Transforms/Utils/Local.h"
Nick Lewyckyf836c892015-07-21 21:56:26 +000028#include <algorithm>
Owen Andersonef9a6fd2008-04-09 08:23:16 +000029using namespace llvm;
30
Chandler Carruth964daaa2014-04-22 02:55:47 +000031#define DEBUG_TYPE "memcpyopt"
32
Owen Andersonef9a6fd2008-04-09 08:23:16 +000033STATISTIC(NumMemCpyInstr, "Number of memcpy instructions deleted");
34STATISTIC(NumMemSetInfer, "Number of memsets inferred");
Duncan Sands0edc7102009-09-03 13:37:16 +000035STATISTIC(NumMoveToCpy, "Number of memmoves converted to memcpy");
Benjamin Kramerea9152e2010-12-24 21:17:12 +000036STATISTIC(NumCpyToSet, "Number of memcpys converted to memset");
Owen Andersonef9a6fd2008-04-09 08:23:16 +000037
Benjamin Kramer15a257d2012-09-13 16:29:49 +000038static int64_t GetOffsetFromIndex(const GEPOperator *GEP, unsigned Idx,
Mehdi Aminia28d91d2015-03-10 02:37:25 +000039 bool &VariableIdxFound,
40 const DataLayout &DL) {
Owen Andersonef9a6fd2008-04-09 08:23:16 +000041 // Skip over the first indices.
42 gep_type_iterator GTI = gep_type_begin(GEP);
43 for (unsigned i = 1; i != Idx; ++i, ++GTI)
44 /*skip along*/;
Nadav Rotem465834c2012-07-24 10:51:42 +000045
Owen Andersonef9a6fd2008-04-09 08:23:16 +000046 // Compute the offset implied by the rest of the indices.
47 int64_t Offset = 0;
48 for (unsigned i = Idx, e = GEP->getNumOperands(); i != e; ++i, ++GTI) {
49 ConstantInt *OpC = dyn_cast<ConstantInt>(GEP->getOperand(i));
Craig Topperf40110f2014-04-25 05:29:35 +000050 if (!OpC)
Owen Andersonef9a6fd2008-04-09 08:23:16 +000051 return VariableIdxFound = true;
52 if (OpC->isZero()) continue; // No offset.
53
54 // Handle struct indices, which add their field offset to the pointer.
Chris Lattner229907c2011-07-18 04:54:35 +000055 if (StructType *STy = dyn_cast<StructType>(*GTI)) {
Mehdi Aminia28d91d2015-03-10 02:37:25 +000056 Offset += DL.getStructLayout(STy)->getElementOffset(OpC->getZExtValue());
Owen Andersonef9a6fd2008-04-09 08:23:16 +000057 continue;
58 }
Nadav Rotem465834c2012-07-24 10:51:42 +000059
Owen Andersonef9a6fd2008-04-09 08:23:16 +000060 // Otherwise, we have a sequential type like an array or vector. Multiply
61 // the index by the ElementSize.
Mehdi Aminia28d91d2015-03-10 02:37:25 +000062 uint64_t Size = DL.getTypeAllocSize(GTI.getIndexedType());
Owen Andersonef9a6fd2008-04-09 08:23:16 +000063 Offset += Size*OpC->getSExtValue();
64 }
65
66 return Offset;
67}
68
Sanjay Patela75c41e2015-08-13 22:53:20 +000069/// Return true if Ptr1 is provably equal to Ptr2 plus a constant offset, and
70/// return that constant offset. For example, Ptr1 might be &A[42], and Ptr2
71/// might be &A[40]. In this case offset would be -8.
Owen Andersonef9a6fd2008-04-09 08:23:16 +000072static bool IsPointerOffset(Value *Ptr1, Value *Ptr2, int64_t &Offset,
Mehdi Aminia28d91d2015-03-10 02:37:25 +000073 const DataLayout &DL) {
Chris Lattnerfa7c29d2011-01-12 01:43:46 +000074 Ptr1 = Ptr1->stripPointerCasts();
75 Ptr2 = Ptr2->stripPointerCasts();
Benjamin Kramer3ef5e462014-03-10 21:05:13 +000076
77 // Handle the trivial case first.
78 if (Ptr1 == Ptr2) {
79 Offset = 0;
80 return true;
81 }
82
Benjamin Kramer15a257d2012-09-13 16:29:49 +000083 GEPOperator *GEP1 = dyn_cast<GEPOperator>(Ptr1);
84 GEPOperator *GEP2 = dyn_cast<GEPOperator>(Ptr2);
Nadav Rotem465834c2012-07-24 10:51:42 +000085
Chris Lattner5120ebf2011-01-08 21:07:56 +000086 bool VariableIdxFound = false;
87
88 // If one pointer is a GEP and the other isn't, then see if the GEP is a
89 // constant offset from the base, as in "P" and "gep P, 1".
Craig Topperf40110f2014-04-25 05:29:35 +000090 if (GEP1 && !GEP2 && GEP1->getOperand(0)->stripPointerCasts() == Ptr2) {
Mehdi Aminia28d91d2015-03-10 02:37:25 +000091 Offset = -GetOffsetFromIndex(GEP1, 1, VariableIdxFound, DL);
Chris Lattner5120ebf2011-01-08 21:07:56 +000092 return !VariableIdxFound;
93 }
94
Craig Topperf40110f2014-04-25 05:29:35 +000095 if (GEP2 && !GEP1 && GEP2->getOperand(0)->stripPointerCasts() == Ptr1) {
Mehdi Aminia28d91d2015-03-10 02:37:25 +000096 Offset = GetOffsetFromIndex(GEP2, 1, VariableIdxFound, DL);
Chris Lattner5120ebf2011-01-08 21:07:56 +000097 return !VariableIdxFound;
98 }
Nadav Rotem465834c2012-07-24 10:51:42 +000099
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000100 // Right now we handle the case when Ptr1/Ptr2 are both GEPs with an identical
101 // base. After that base, they may have some number of common (and
102 // potentially variable) indices. After that they handle some constant
103 // offset, which determines their offset from each other. At this point, we
104 // handle no other case.
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000105 if (!GEP1 || !GEP2 || GEP1->getOperand(0) != GEP2->getOperand(0))
106 return false;
Nadav Rotem465834c2012-07-24 10:51:42 +0000107
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000108 // Skip any common indices and track the GEP types.
109 unsigned Idx = 1;
110 for (; Idx != GEP1->getNumOperands() && Idx != GEP2->getNumOperands(); ++Idx)
111 if (GEP1->getOperand(Idx) != GEP2->getOperand(Idx))
112 break;
113
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000114 int64_t Offset1 = GetOffsetFromIndex(GEP1, Idx, VariableIdxFound, DL);
115 int64_t Offset2 = GetOffsetFromIndex(GEP2, Idx, VariableIdxFound, DL);
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000116 if (VariableIdxFound) return false;
Nadav Rotem465834c2012-07-24 10:51:42 +0000117
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000118 Offset = Offset2-Offset1;
119 return true;
120}
121
122
Sanjay Patela75c41e2015-08-13 22:53:20 +0000123/// Represents a range of memset'd bytes with the ByteVal value.
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000124/// This allows us to analyze stores like:
125/// store 0 -> P+1
126/// store 0 -> P+0
127/// store 0 -> P+3
128/// store 0 -> P+2
129/// which sometimes happens with stores to arrays of structs etc. When we see
130/// the first store, we make a range [1, 2). The second store extends the range
131/// to [0, 2). The third makes a new range [2, 3). The fourth store joins the
132/// two ranges into [0, 3) which is memset'able.
133namespace {
Tim Northover39617352016-05-10 21:49:40 +0000134struct MemsetRange {
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000135 // Start/End - A semi range that describes the span that this range covers.
Nadav Rotem465834c2012-07-24 10:51:42 +0000136 // The range is closed at the start and open at the end: [Start, End).
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000137 int64_t Start, End;
138
139 /// StartPtr - The getelementptr instruction that points to the start of the
140 /// range.
Tim Northover39617352016-05-10 21:49:40 +0000141 Value *StartPtr;
Nadav Rotem465834c2012-07-24 10:51:42 +0000142
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000143 /// Alignment - The known alignment of the first store.
144 unsigned Alignment;
Nadav Rotem465834c2012-07-24 10:51:42 +0000145
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000146 /// TheStores - The actual stores that make up this range.
Chris Lattner4dc1fd92011-01-08 20:54:51 +0000147 SmallVector<Instruction*, 16> TheStores;
Nadav Rotem465834c2012-07-24 10:51:42 +0000148
Tim Northover39617352016-05-10 21:49:40 +0000149 bool isProfitableToUseMemset(const DataLayout &DL) const;
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000150};
Alexander Kornienkof00654e2015-06-23 09:49:53 +0000151} // end anon namespace
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000152
Tim Northover39617352016-05-10 21:49:40 +0000153bool MemsetRange::isProfitableToUseMemset(const DataLayout &DL) const {
154 // If we found more than 4 stores to merge or 16 bytes, use memset.
Chad Rosier19446a02011-12-05 22:37:00 +0000155 if (TheStores.size() >= 4 || End-Start >= 16) return true;
Chris Lattner4dc1fd92011-01-08 20:54:51 +0000156
157 // If there is nothing to merge, don't do anything.
158 if (TheStores.size() < 2) return false;
Nadav Rotem465834c2012-07-24 10:51:42 +0000159
Tim Northover39617352016-05-10 21:49:40 +0000160 // If any of the stores are a memset, then it is always good to extend the
161 // memset.
Craig Toppere325e382015-11-20 07:18:48 +0000162 for (Instruction *SI : TheStores)
Tim Northover39617352016-05-10 21:49:40 +0000163 if (!isa<StoreInst>(SI))
Chris Lattner4dc1fd92011-01-08 20:54:51 +0000164 return true;
Nadav Rotem465834c2012-07-24 10:51:42 +0000165
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000166 // Assume that the code generator is capable of merging pairs of stores
167 // together if it wants to.
Chris Lattner4dc1fd92011-01-08 20:54:51 +0000168 if (TheStores.size() == 2) return false;
Nadav Rotem465834c2012-07-24 10:51:42 +0000169
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000170 // If we have fewer than 8 stores, it can still be worthwhile to do this.
171 // For example, merging 4 i8 stores into an i32 store is useful almost always.
172 // However, merging 2 32-bit stores isn't useful on a 32-bit architecture (the
173 // memset will be split into 2 32-bit stores anyway) and doing so can
174 // pessimize the llvm optimizer.
175 //
176 // Since we don't have perfect knowledge here, make some assumptions: assume
Matt Arsenault899f7d22013-09-16 22:43:16 +0000177 // the maximum GPR width is the same size as the largest legal integer
178 // size. If so, check to see whether we will end up actually reducing the
179 // number of stores used.
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000180 unsigned Bytes = unsigned(End-Start);
Jun Bum Limbe11bdc2016-05-13 18:38:35 +0000181 unsigned MaxIntSize = DL.getLargestLegalIntTypeSizeInBits() / 8;
Matt Arsenault899f7d22013-09-16 22:43:16 +0000182 if (MaxIntSize == 0)
183 MaxIntSize = 1;
184 unsigned NumPointerStores = Bytes / MaxIntSize;
Nadav Rotem465834c2012-07-24 10:51:42 +0000185
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000186 // Assume the remaining bytes if any are done a byte at a time.
Craig Toppera5ea5282015-11-21 17:44:42 +0000187 unsigned NumByteStores = Bytes % MaxIntSize;
Nadav Rotem465834c2012-07-24 10:51:42 +0000188
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000189 // If we will reduce the # stores (according to this heuristic), do the
190 // transformation. This encourages merging 4 x i8 -> i32 and 2 x i16 -> i32
191 // etc.
192 return TheStores.size() > NumPointerStores+NumByteStores;
Nadav Rotem465834c2012-07-24 10:51:42 +0000193}
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000194
195
196namespace {
Tim Northover39617352016-05-10 21:49:40 +0000197class MemsetRanges {
Sanjay Patela75c41e2015-08-13 22:53:20 +0000198 /// A sorted list of the memset ranges.
Tim Northover39617352016-05-10 21:49:40 +0000199 SmallVector<MemsetRange, 8> Ranges;
200 typedef SmallVectorImpl<MemsetRange>::iterator range_iterator;
Rafael Espindola37dc9e12014-02-21 00:06:31 +0000201 const DataLayout &DL;
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000202public:
Tim Northover39617352016-05-10 21:49:40 +0000203 MemsetRanges(const DataLayout &DL) : DL(DL) {}
Nadav Rotem465834c2012-07-24 10:51:42 +0000204
Tim Northover39617352016-05-10 21:49:40 +0000205 typedef SmallVectorImpl<MemsetRange>::const_iterator const_iterator;
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000206 const_iterator begin() const { return Ranges.begin(); }
207 const_iterator end() const { return Ranges.end(); }
208 bool empty() const { return Ranges.empty(); }
Nadav Rotem465834c2012-07-24 10:51:42 +0000209
Chris Lattnerc6381472011-01-08 20:24:01 +0000210 void addInst(int64_t OffsetFromFirst, Instruction *Inst) {
Chris Lattner4dc1fd92011-01-08 20:54:51 +0000211 if (StoreInst *SI = dyn_cast<StoreInst>(Inst))
212 addStore(OffsetFromFirst, SI);
213 else
214 addMemSet(OffsetFromFirst, cast<MemSetInst>(Inst));
Chris Lattnerc6381472011-01-08 20:24:01 +0000215 }
Chris Lattner4dc1fd92011-01-08 20:54:51 +0000216
217 void addStore(int64_t OffsetFromFirst, StoreInst *SI) {
Rafael Espindola37dc9e12014-02-21 00:06:31 +0000218 int64_t StoreSize = DL.getTypeStoreSize(SI->getOperand(0)->getType());
Nadav Rotem465834c2012-07-24 10:51:42 +0000219
Chris Lattner4dc1fd92011-01-08 20:54:51 +0000220 addRange(OffsetFromFirst, StoreSize,
Tim Northover39617352016-05-10 21:49:40 +0000221 SI->getPointerOperand(), SI->getAlignment(), SI);
Chris Lattner4dc1fd92011-01-08 20:54:51 +0000222 }
Nadav Rotem465834c2012-07-24 10:51:42 +0000223
Chris Lattner4dc1fd92011-01-08 20:54:51 +0000224 void addMemSet(int64_t OffsetFromFirst, MemSetInst *MSI) {
225 int64_t Size = cast<ConstantInt>(MSI->getLength())->getZExtValue();
Tim Northover39617352016-05-10 21:49:40 +0000226 addRange(OffsetFromFirst, Size, MSI->getDest(), MSI->getAlignment(), MSI);
Chris Lattner4dc1fd92011-01-08 20:54:51 +0000227 }
Nadav Rotem465834c2012-07-24 10:51:42 +0000228
Tim Northover39617352016-05-10 21:49:40 +0000229 void addRange(int64_t Start, int64_t Size, Value *Ptr,
Chris Lattner4dc1fd92011-01-08 20:54:51 +0000230 unsigned Alignment, Instruction *Inst);
231
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000232};
Nadav Rotem465834c2012-07-24 10:51:42 +0000233
Alexander Kornienkof00654e2015-06-23 09:49:53 +0000234} // end anon namespace
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000235
236
Tim Northover39617352016-05-10 21:49:40 +0000237/// Add a new store to the MemsetRanges data structure. This adds a
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000238/// new range for the specified store at the specified offset, merging into
239/// existing ranges as appropriate.
Tim Northover39617352016-05-10 21:49:40 +0000240void MemsetRanges::addRange(int64_t Start, int64_t Size, Value *Ptr,
241 unsigned Alignment, Instruction *Inst) {
Chris Lattner4dc1fd92011-01-08 20:54:51 +0000242 int64_t End = Start+Size;
Nadav Rotem465834c2012-07-24 10:51:42 +0000243
Nick Lewyckyf836c892015-07-21 21:56:26 +0000244 range_iterator I = std::lower_bound(Ranges.begin(), Ranges.end(), Start,
Tim Northover39617352016-05-10 21:49:40 +0000245 [](const MemsetRange &LHS, int64_t RHS) { return LHS.End < RHS; });
Nadav Rotem465834c2012-07-24 10:51:42 +0000246
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000247 // We now know that I == E, in which case we didn't find anything to merge
248 // with, or that Start <= I->End. If End < I->Start or I == E, then we need
249 // to insert a new range. Handle this now.
Nick Lewyckyf836c892015-07-21 21:56:26 +0000250 if (I == Ranges.end() || End < I->Start) {
Tim Northover39617352016-05-10 21:49:40 +0000251 MemsetRange &R = *Ranges.insert(I, MemsetRange());
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000252 R.Start = Start;
253 R.End = End;
Tim Northover39617352016-05-10 21:49:40 +0000254 R.StartPtr = Ptr;
Chris Lattner4dc1fd92011-01-08 20:54:51 +0000255 R.Alignment = Alignment;
256 R.TheStores.push_back(Inst);
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000257 return;
258 }
Nadav Rotem465834c2012-07-24 10:51:42 +0000259
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000260 // This store overlaps with I, add it.
Chris Lattner4dc1fd92011-01-08 20:54:51 +0000261 I->TheStores.push_back(Inst);
Nadav Rotem465834c2012-07-24 10:51:42 +0000262
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000263 // At this point, we may have an interval that completely contains our store.
264 // If so, just add it to the interval and return.
265 if (I->Start <= Start && I->End >= End)
266 return;
Nadav Rotem465834c2012-07-24 10:51:42 +0000267
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000268 // Now we know that Start <= I->End and End >= I->Start so the range overlaps
269 // but is not entirely contained within the range.
Nadav Rotem465834c2012-07-24 10:51:42 +0000270
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000271 // See if the range extends the start of the range. In this case, it couldn't
272 // possibly cause it to join the prior range, because otherwise we would have
273 // stopped on *it*.
274 if (Start < I->Start) {
275 I->Start = Start;
Tim Northover39617352016-05-10 21:49:40 +0000276 I->StartPtr = Ptr;
Chris Lattner4dc1fd92011-01-08 20:54:51 +0000277 I->Alignment = Alignment;
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000278 }
Nadav Rotem465834c2012-07-24 10:51:42 +0000279
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000280 // Now we know that Start <= I->End and Start >= I->Start (so the startpoint
281 // is in or right at the end of I), and that End >= I->Start. Extend I out to
282 // End.
283 if (End > I->End) {
284 I->End = End;
Nick Lewyckybfd4ad62009-03-19 05:51:39 +0000285 range_iterator NextI = I;
Nick Lewyckyf836c892015-07-21 21:56:26 +0000286 while (++NextI != Ranges.end() && End >= NextI->Start) {
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000287 // Merge the range in.
288 I->TheStores.append(NextI->TheStores.begin(), NextI->TheStores.end());
289 if (NextI->End > I->End)
290 I->End = NextI->End;
291 Ranges.erase(NextI);
292 NextI = I;
293 }
294 }
295}
296
297//===----------------------------------------------------------------------===//
Sean Silva6347df02016-06-14 02:44:55 +0000298// MemCpyOptLegacyPass Pass
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000299//===----------------------------------------------------------------------===//
300
301namespace {
Sean Silva6347df02016-06-14 02:44:55 +0000302 class MemCpyOptLegacyPass : public FunctionPass {
303 MemCpyOptPass Impl;
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000304 public:
305 static char ID; // Pass identification, replacement for typeid
Sean Silva6347df02016-06-14 02:44:55 +0000306 MemCpyOptLegacyPass() : FunctionPass(ID) {
307 initializeMemCpyOptLegacyPassPass(*PassRegistry::getPassRegistry());
Owen Anderson6c18d1a2010-10-19 17:21:58 +0000308 }
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000309
Craig Topper3e4c6972014-03-05 09:10:37 +0000310 bool runOnFunction(Function &F) override;
Chris Lattnerc6381472011-01-08 20:24:01 +0000311
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000312 private:
313 // This transformation requires dominator postdominator info
Craig Topper3e4c6972014-03-05 09:10:37 +0000314 void getAnalysisUsage(AnalysisUsage &AU) const override {
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000315 AU.setPreservesCFG();
Chandler Carruth66b31302015-01-04 12:03:27 +0000316 AU.addRequired<AssumptionCacheTracker>();
Chandler Carruth73523022014-01-13 13:07:17 +0000317 AU.addRequired<DominatorTreeWrapperPass>();
Chandler Carruth61440d22016-03-10 00:55:30 +0000318 AU.addRequired<MemoryDependenceWrapperPass>();
Chandler Carruth7b560d42015-09-09 17:55:00 +0000319 AU.addRequired<AAResultsWrapperPass>();
Chandler Carruthb98f63d2015-01-15 10:41:28 +0000320 AU.addRequired<TargetLibraryInfoWrapperPass>();
Chandler Carruth7b560d42015-09-09 17:55:00 +0000321 AU.addPreserved<GlobalsAAWrapperPass>();
Chandler Carruth61440d22016-03-10 00:55:30 +0000322 AU.addPreserved<MemoryDependenceWrapperPass>();
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000323 }
Nadav Rotem465834c2012-07-24 10:51:42 +0000324
Matt Walaa4afccd2015-06-12 18:16:51 +0000325 // Helper functions
Chris Lattnerb5557a72009-09-01 17:09:55 +0000326 bool processStore(StoreInst *SI, BasicBlock::iterator &BBI);
Chris Lattner9a1d63b2011-01-08 21:19:19 +0000327 bool processMemSet(MemSetInst *SI, BasicBlock::iterator &BBI);
Tim Northover39617352016-05-10 21:49:40 +0000328 bool processMemCpy(MemCpyInst *M);
Chris Lattner1145e332009-09-01 17:56:32 +0000329 bool processMemMove(MemMoveInst *M);
Owen Anderson18e4fed2010-10-15 22:52:12 +0000330 bool performCallSlotOptzn(Instruction *cpy, Value *cpyDst, Value *cpySrc,
Duncan Sandsc6ada692012-10-04 10:54:40 +0000331 uint64_t cpyLen, unsigned cpyAlign, CallInst *C);
Ahmed Bougacha15a31f62015-05-16 01:23:47 +0000332 bool processMemCpyMemCpyDependence(MemCpyInst *M, MemCpyInst *MDep);
Ahmed Bougacha83f78a42015-04-17 22:20:57 +0000333 bool processMemSetMemCpyDependence(MemCpyInst *M, MemSetInst *MDep);
Ahmed Bougachaf8fa3b82015-05-16 01:32:26 +0000334 bool performMemCpyToMemSetOptzn(MemCpyInst *M, MemSetInst *MDep);
Chris Lattner58f9f582010-11-21 00:28:59 +0000335 bool processByValArgument(CallSite CS, unsigned ArgNo);
Chris Lattnerc6381472011-01-08 20:24:01 +0000336 Instruction *tryMergingIntoMemset(Instruction *I, Value *StartPtr,
337 Value *ByteVal);
338
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000339 bool iterateOnFunction(Function &F);
340 };
Nadav Rotem465834c2012-07-24 10:51:42 +0000341
Sean Silva6347df02016-06-14 02:44:55 +0000342 char MemCpyOptLegacyPass::ID = 0;
Alexander Kornienkof00654e2015-06-23 09:49:53 +0000343}
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000344
Sanjay Patela75c41e2015-08-13 22:53:20 +0000345/// The public interface to this file...
Sean Silva6347df02016-06-14 02:44:55 +0000346FunctionPass *llvm::createMemCpyOptPass() { return new MemCpyOptLegacyPass(); }
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000347
Sean Silva6347df02016-06-14 02:44:55 +0000348INITIALIZE_PASS_BEGIN(MemCpyOptLegacyPass, "memcpyopt", "MemCpy Optimization",
Owen Anderson8ac477f2010-10-12 19:48:12 +0000349 false, false)
Chandler Carruth66b31302015-01-04 12:03:27 +0000350INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
Chandler Carruth73523022014-01-13 13:07:17 +0000351INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
Chandler Carruth61440d22016-03-10 00:55:30 +0000352INITIALIZE_PASS_DEPENDENCY(MemoryDependenceWrapperPass)
Chandler Carruthb98f63d2015-01-15 10:41:28 +0000353INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
Chandler Carruth7b560d42015-09-09 17:55:00 +0000354INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
355INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
Sean Silva6347df02016-06-14 02:44:55 +0000356INITIALIZE_PASS_END(MemCpyOptLegacyPass, "memcpyopt", "MemCpy Optimization",
Owen Anderson8ac477f2010-10-12 19:48:12 +0000357 false, false)
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000358
Sanjay Patela75c41e2015-08-13 22:53:20 +0000359/// When scanning forward over instructions, we look for some other patterns to
360/// fold away. In particular, this looks for stores to neighboring locations of
361/// memory. If it sees enough consecutive ones, it attempts to merge them
362/// together into a memcpy/memset.
Sean Silva6347df02016-06-14 02:44:55 +0000363Instruction *MemCpyOptPass::tryMergingIntoMemset(Instruction *StartInst,
364 Value *StartPtr,
365 Value *ByteVal) {
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000366 const DataLayout &DL = StartInst->getModule()->getDataLayout();
Nadav Rotem465834c2012-07-24 10:51:42 +0000367
Chris Lattnerc6381472011-01-08 20:24:01 +0000368 // Okay, so we now have a single store that can be splatable. Scan to find
369 // all subsequent stores of the same value to offset from the same pointer.
370 // Join these together into ranges, so we can decide whether contiguous blocks
371 // are stored.
Tim Northover39617352016-05-10 21:49:40 +0000372 MemsetRanges Ranges(DL);
Nadav Rotem465834c2012-07-24 10:51:42 +0000373
Duncan P. N. Exon Smithbe4d8cb2015-10-13 19:26:58 +0000374 BasicBlock::iterator BI(StartInst);
Chris Lattnerc6381472011-01-08 20:24:01 +0000375 for (++BI; !isa<TerminatorInst>(BI); ++BI) {
Chris Lattner4dc1fd92011-01-08 20:54:51 +0000376 if (!isa<StoreInst>(BI) && !isa<MemSetInst>(BI)) {
377 // If the instruction is readnone, ignore it, otherwise bail out. We
378 // don't even allow readonly here because we don't want something like:
Chris Lattnerc6381472011-01-08 20:24:01 +0000379 // A[1] = 2; strlen(A); A[2] = 2; -> memcpy(A, ...); strlen(A).
Chris Lattner4dc1fd92011-01-08 20:54:51 +0000380 if (BI->mayWriteToMemory() || BI->mayReadFromMemory())
381 break;
382 continue;
383 }
Nadav Rotem465834c2012-07-24 10:51:42 +0000384
Chris Lattner4dc1fd92011-01-08 20:54:51 +0000385 if (StoreInst *NextStore = dyn_cast<StoreInst>(BI)) {
386 // If this is a store, see if we can merge it in.
Eli Friedman9a468152011-08-17 22:22:24 +0000387 if (!NextStore->isSimple()) break;
Nadav Rotem465834c2012-07-24 10:51:42 +0000388
Chris Lattner4dc1fd92011-01-08 20:54:51 +0000389 // Check to see if this stored value is of the same byte-splattable value.
390 if (ByteVal != isBytewiseValue(NextStore->getOperand(0)))
391 break;
Nadav Rotem465834c2012-07-24 10:51:42 +0000392
Chris Lattner4dc1fd92011-01-08 20:54:51 +0000393 // Check to see if this store is to a constant offset from the start ptr.
394 int64_t Offset;
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000395 if (!IsPointerOffset(StartPtr, NextStore->getPointerOperand(), Offset,
396 DL))
Chris Lattner4dc1fd92011-01-08 20:54:51 +0000397 break;
Nadav Rotem465834c2012-07-24 10:51:42 +0000398
Chris Lattner4dc1fd92011-01-08 20:54:51 +0000399 Ranges.addStore(Offset, NextStore);
400 } else {
401 MemSetInst *MSI = cast<MemSetInst>(BI);
Nadav Rotem465834c2012-07-24 10:51:42 +0000402
Chris Lattner4dc1fd92011-01-08 20:54:51 +0000403 if (MSI->isVolatile() || ByteVal != MSI->getValue() ||
404 !isa<ConstantInt>(MSI->getLength()))
405 break;
Nadav Rotem465834c2012-07-24 10:51:42 +0000406
Chris Lattner4dc1fd92011-01-08 20:54:51 +0000407 // Check to see if this store is to a constant offset from the start ptr.
408 int64_t Offset;
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000409 if (!IsPointerOffset(StartPtr, MSI->getDest(), Offset, DL))
Chris Lattner4dc1fd92011-01-08 20:54:51 +0000410 break;
Nadav Rotem465834c2012-07-24 10:51:42 +0000411
Chris Lattner4dc1fd92011-01-08 20:54:51 +0000412 Ranges.addMemSet(Offset, MSI);
413 }
Chris Lattnerc6381472011-01-08 20:24:01 +0000414 }
Nadav Rotem465834c2012-07-24 10:51:42 +0000415
Chris Lattnerc6381472011-01-08 20:24:01 +0000416 // If we have no ranges, then we just had a single store with nothing that
417 // could be merged in. This is a very common case of course.
418 if (Ranges.empty())
Craig Topperf40110f2014-04-25 05:29:35 +0000419 return nullptr;
Nadav Rotem465834c2012-07-24 10:51:42 +0000420
Chris Lattnerc6381472011-01-08 20:24:01 +0000421 // If we had at least one store that could be merged in, add the starting
422 // store as well. We try to avoid this unless there is at least something
423 // interesting as a small compile-time optimization.
424 Ranges.addInst(0, StartInst);
425
426 // If we create any memsets, we put it right before the first instruction that
427 // isn't part of the memset block. This ensure that the memset is dominated
428 // by any addressing instruction needed by the start of the block.
Duncan P. N. Exon Smithbe4d8cb2015-10-13 19:26:58 +0000429 IRBuilder<> Builder(&*BI);
Chris Lattnerc6381472011-01-08 20:24:01 +0000430
431 // Now that we have full information about ranges, loop over the ranges and
432 // emit memset's for anything big enough to be worthwhile.
Craig Topperf40110f2014-04-25 05:29:35 +0000433 Instruction *AMemSet = nullptr;
Tim Northover39617352016-05-10 21:49:40 +0000434 for (const MemsetRange &Range : Ranges) {
Nadav Rotem465834c2012-07-24 10:51:42 +0000435
Chris Lattnerc6381472011-01-08 20:24:01 +0000436 if (Range.TheStores.size() == 1) continue;
Nadav Rotem465834c2012-07-24 10:51:42 +0000437
Chris Lattnerc6381472011-01-08 20:24:01 +0000438 // If it is profitable to lower this range to memset, do so now.
Tim Northover39617352016-05-10 21:49:40 +0000439 if (!Range.isProfitableToUseMemset(DL))
Chris Lattnerc6381472011-01-08 20:24:01 +0000440 continue;
Nadav Rotem465834c2012-07-24 10:51:42 +0000441
Chris Lattnerc6381472011-01-08 20:24:01 +0000442 // Otherwise, we do want to transform this! Create a new memset.
443 // Get the starting pointer of the block.
Tim Northover39617352016-05-10 21:49:40 +0000444 StartPtr = Range.StartPtr;
Nadav Rotem465834c2012-07-24 10:51:42 +0000445
Tim Northover39617352016-05-10 21:49:40 +0000446 // Determine alignment
447 unsigned Alignment = Range.Alignment;
448 if (Alignment == 0) {
449 Type *EltType =
450 cast<PointerType>(StartPtr->getType())->getElementType();
451 Alignment = DL.getABITypeAlignment(EltType);
452 }
453
454 AMemSet =
455 Builder.CreateMemSet(StartPtr, ByteVal, Range.End-Range.Start, Alignment);
Nadav Rotem465834c2012-07-24 10:51:42 +0000456
Chris Lattnerc6381472011-01-08 20:24:01 +0000457 DEBUG(dbgs() << "Replace stores:\n";
Craig Toppere325e382015-11-20 07:18:48 +0000458 for (Instruction *SI : Range.TheStores)
459 dbgs() << *SI << '\n';
Chris Lattnerc6381472011-01-08 20:24:01 +0000460 dbgs() << "With: " << *AMemSet << '\n');
Devang Patelc7e4fa72011-05-04 21:58:58 +0000461
462 if (!Range.TheStores.empty())
463 AMemSet->setDebugLoc(Range.TheStores[0]->getDebugLoc());
464
Chris Lattnerc6381472011-01-08 20:24:01 +0000465 // Zap all the stores.
Craig Toppere325e382015-11-20 07:18:48 +0000466 for (Instruction *SI : Range.TheStores) {
467 MD->removeInstruction(SI);
468 SI->eraseFromParent();
Chris Lattner7d6433a2011-01-08 22:19:21 +0000469 }
Chris Lattnerc6381472011-01-08 20:24:01 +0000470 ++NumMemSetInfer;
471 }
Nadav Rotem465834c2012-07-24 10:51:42 +0000472
Chris Lattnerc6381472011-01-08 20:24:01 +0000473 return AMemSet;
474}
475
Tim Northover39617352016-05-10 21:49:40 +0000476static unsigned findCommonAlignment(const DataLayout &DL, const StoreInst *SI,
477 const LoadInst *LI) {
478 unsigned StoreAlign = SI->getAlignment();
479 if (!StoreAlign)
480 StoreAlign = DL.getABITypeAlignment(SI->getOperand(0)->getType());
481 unsigned LoadAlign = LI->getAlignment();
482 if (!LoadAlign)
483 LoadAlign = DL.getABITypeAlignment(LI->getType());
Amaury Secheta0c242c2016-01-05 20:17:48 +0000484
Tim Northover39617352016-05-10 21:49:40 +0000485 return std::min(StoreAlign, LoadAlign);
Amaury Secheta0c242c2016-01-05 20:17:48 +0000486}
Chris Lattnerc6381472011-01-08 20:24:01 +0000487
Amaury Sechetbdb261b2016-03-14 22:52:27 +0000488// This method try to lift a store instruction before position P.
489// It will lift the store and its argument + that anything that
David Majnemerd99068d2016-05-26 19:24:24 +0000490// may alias with these.
Amaury Sechetbdb261b2016-03-14 22:52:27 +0000491// The method returns true if it was successful.
492static bool moveUp(AliasAnalysis &AA, StoreInst *SI, Instruction *P) {
493 // If the store alias this position, early bail out.
494 MemoryLocation StoreLoc = MemoryLocation::get(SI);
495 if (AA.getModRefInfo(P, StoreLoc) != MRI_NoModRef)
496 return false;
497
498 // Keep track of the arguments of all instruction we plan to lift
499 // so we can make sure to lift them as well if apropriate.
500 DenseSet<Instruction*> Args;
501 if (auto *Ptr = dyn_cast<Instruction>(SI->getPointerOperand()))
502 if (Ptr->getParent() == SI->getParent())
503 Args.insert(Ptr);
504
505 // Instruction to lift before P.
506 SmallVector<Instruction*, 8> ToLift;
507
508 // Memory locations of lifted instructions.
509 SmallVector<MemoryLocation, 8> MemLocs;
510 MemLocs.push_back(StoreLoc);
511
512 // Lifted callsites.
513 SmallVector<ImmutableCallSite, 8> CallSites;
514
515 for (auto I = --SI->getIterator(), E = P->getIterator(); I != E; --I) {
516 auto *C = &*I;
517
518 bool MayAlias = AA.getModRefInfo(C) != MRI_NoModRef;
519
520 bool NeedLift = false;
521 if (Args.erase(C))
522 NeedLift = true;
523 else if (MayAlias) {
524 NeedLift = std::any_of(MemLocs.begin(), MemLocs.end(),
525 [C, &AA](const MemoryLocation &ML) {
526 return AA.getModRefInfo(C, ML);
527 });
528
529 if (!NeedLift)
530 NeedLift = std::any_of(CallSites.begin(), CallSites.end(),
531 [C, &AA](const ImmutableCallSite &CS) {
532 return AA.getModRefInfo(C, CS);
533 });
534 }
535
536 if (!NeedLift)
537 continue;
538
539 if (MayAlias) {
540 if (auto CS = ImmutableCallSite(C)) {
541 // If we can't lift this before P, it's game over.
542 if (AA.getModRefInfo(P, CS) != MRI_NoModRef)
543 return false;
544
545 CallSites.push_back(CS);
546 } else if (isa<LoadInst>(C) || isa<StoreInst>(C) || isa<VAArgInst>(C)) {
547 // If we can't lift this before P, it's game over.
548 auto ML = MemoryLocation::get(C);
549 if (AA.getModRefInfo(P, ML) != MRI_NoModRef)
550 return false;
551
552 MemLocs.push_back(ML);
553 } else
554 // We don't know how to lift this instruction.
555 return false;
556 }
557
558 ToLift.push_back(C);
559 for (unsigned k = 0, e = C->getNumOperands(); k != e; ++k)
560 if (auto *A = dyn_cast<Instruction>(C->getOperand(k)))
561 if (A->getParent() == SI->getParent())
562 Args.insert(A);
563 }
564
565 // We made it, we need to lift
566 for (auto *I : reverse(ToLift)) {
567 DEBUG(dbgs() << "Lifting " << *I << " before " << *P << "\n");
568 I->moveBefore(P);
569 }
570
571 return true;
572}
573
Sean Silva6347df02016-06-14 02:44:55 +0000574bool MemCpyOptPass::processStore(StoreInst *SI, BasicBlock::iterator &BBI) {
Eli Friedman9a468152011-08-17 22:22:24 +0000575 if (!SI->isSimple()) return false;
Andrea Di Biagio99493df2015-10-09 10:53:41 +0000576
577 // Avoid merging nontemporal stores since the resulting
578 // memcpy/memset would not be able to preserve the nontemporal hint.
579 // In theory we could teach how to propagate the !nontemporal metadata to
580 // memset calls. However, that change would force the backend to
581 // conservatively expand !nontemporal memset calls back to sequences of
582 // store instructions (effectively undoing the merging).
583 if (SI->getMetadata(LLVMContext::MD_nontemporal))
584 return false;
585
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000586 const DataLayout &DL = SI->getModule()->getDataLayout();
Owen Anderson18e4fed2010-10-15 22:52:12 +0000587
Amaury Secheta0c242c2016-01-05 20:17:48 +0000588 // Load to store forwarding can be interpreted as memcpy.
Owen Anderson18e4fed2010-10-15 22:52:12 +0000589 if (LoadInst *LI = dyn_cast<LoadInst>(SI->getOperand(0))) {
Eli Friedman9a468152011-08-17 22:22:24 +0000590 if (LI->isSimple() && LI->hasOneUse() &&
Eli Friedmane8bbc102011-06-15 01:25:56 +0000591 LI->getParent() == SI->getParent()) {
Amaury Secheta0c242c2016-01-05 20:17:48 +0000592
593 auto *T = LI->getType();
594 if (T->isAggregateType()) {
Sean Silva6347df02016-06-14 02:44:55 +0000595 AliasAnalysis &AA = LookupAliasAnalysis();
Amaury Secheta0c242c2016-01-05 20:17:48 +0000596 MemoryLocation LoadLoc = MemoryLocation::get(LI);
597
598 // We use alias analysis to check if an instruction may store to
599 // the memory we load from in between the load and the store. If
Amaury Sechetd3b2c0f2016-01-06 09:30:39 +0000600 // such an instruction is found, we try to promote there instead
601 // of at the store position.
602 Instruction *P = SI;
Amaury Sechetbdb261b2016-03-14 22:52:27 +0000603 for (auto &I : make_range(++LI->getIterator(), SI->getIterator())) {
604 if (AA.getModRefInfo(&I, LoadLoc) & MRI_Mod) {
605 P = &I;
606 break;
Amaury Secheta0c242c2016-01-05 20:17:48 +0000607 }
Amaury Sechetbdb261b2016-03-14 22:52:27 +0000608 }
Amaury Sechetd3b2c0f2016-01-06 09:30:39 +0000609
Amaury Sechetbdb261b2016-03-14 22:52:27 +0000610 // We found an instruction that may write to the loaded memory.
611 // We can try to promote at this position instead of the store
612 // position if nothing alias the store memory after this and the store
613 // destination is not in the range.
614 if (P && P != SI) {
615 if (!moveUp(AA, SI, P))
616 P = nullptr;
Amaury Secheta0c242c2016-01-05 20:17:48 +0000617 }
618
Amaury Sechetd3b2c0f2016-01-06 09:30:39 +0000619 // If a valid insertion position is found, then we can promote
620 // the load/store pair to a memcpy.
621 if (P) {
Amaury Secheta0c242c2016-01-05 20:17:48 +0000622 // If we load from memory that may alias the memory we store to,
623 // memmove must be used to preserve semantic. If not, memcpy can
624 // be used.
625 bool UseMemMove = false;
626 if (!AA.isNoAlias(MemoryLocation::get(SI), LoadLoc))
627 UseMemMove = true;
628
629 unsigned Align = findCommonAlignment(DL, SI, LI);
630 uint64_t Size = DL.getTypeStoreSize(T);
631
Amaury Sechetd3b2c0f2016-01-06 09:30:39 +0000632 IRBuilder<> Builder(P);
Amaury Secheta0c242c2016-01-05 20:17:48 +0000633 Instruction *M;
634 if (UseMemMove)
635 M = Builder.CreateMemMove(SI->getPointerOperand(),
636 LI->getPointerOperand(), Size,
637 Align, SI->isVolatile());
638 else
639 M = Builder.CreateMemCpy(SI->getPointerOperand(),
640 LI->getPointerOperand(), Size,
641 Align, SI->isVolatile());
642
643 DEBUG(dbgs() << "Promoting " << *LI << " to " << *SI
644 << " => " << *M << "\n");
645
646 MD->removeInstruction(SI);
647 SI->eraseFromParent();
648 MD->removeInstruction(LI);
649 LI->eraseFromParent();
650 ++NumMemCpyInstr;
651
652 // Make sure we do not invalidate the iterator.
653 BBI = M->getIterator();
654 return true;
655 }
656 }
657
658 // Detect cases where we're performing call slot forwarding, but
659 // happen to be using a load-store pair to implement it, rather than
660 // a memcpy.
Eli Friedman5da0ff42011-06-02 21:24:42 +0000661 MemDepResult ldep = MD->getDependency(LI);
Craig Topperf40110f2014-04-25 05:29:35 +0000662 CallInst *C = nullptr;
Eli Friedman5da0ff42011-06-02 21:24:42 +0000663 if (ldep.isClobber() && !isa<MemCpyInst>(ldep.getInst()))
664 C = dyn_cast<CallInst>(ldep.getInst());
665
666 if (C) {
667 // Check that nothing touches the dest of the "copy" between
668 // the call and the store.
David Majnemerd99068d2016-05-26 19:24:24 +0000669 Value *CpyDest = SI->getPointerOperand()->stripPointerCasts();
670 bool CpyDestIsLocal = isa<AllocaInst>(CpyDest);
Sean Silva6347df02016-06-14 02:44:55 +0000671 AliasAnalysis &AA = LookupAliasAnalysis();
Chandler Carruthac80dc72015-06-17 07:18:54 +0000672 MemoryLocation StoreLoc = MemoryLocation::get(SI);
Duncan P. N. Exon Smithbe4d8cb2015-10-13 19:26:58 +0000673 for (BasicBlock::iterator I = --SI->getIterator(), E = C->getIterator();
674 I != E; --I) {
Chandler Carruth194f59c2015-07-22 23:15:57 +0000675 if (AA.getModRefInfo(&*I, StoreLoc) != MRI_NoModRef) {
Craig Topperf40110f2014-04-25 05:29:35 +0000676 C = nullptr;
Eli Friedmane8bbc102011-06-15 01:25:56 +0000677 break;
678 }
David Majnemerd99068d2016-05-26 19:24:24 +0000679 // The store to dest may never happen if an exception can be thrown
680 // between the load and the store.
681 if (I->mayThrow() && !CpyDestIsLocal) {
682 C = nullptr;
683 break;
684 }
Eli Friedman5da0ff42011-06-02 21:24:42 +0000685 }
686 }
687
Owen Anderson18e4fed2010-10-15 22:52:12 +0000688 if (C) {
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000689 bool changed = performCallSlotOptzn(
690 LI, SI->getPointerOperand()->stripPointerCasts(),
691 LI->getPointerOperand()->stripPointerCasts(),
692 DL.getTypeStoreSize(SI->getOperand(0)->getType()),
Amaury Secheta0c242c2016-01-05 20:17:48 +0000693 findCommonAlignment(DL, SI, LI), C);
Owen Anderson18e4fed2010-10-15 22:52:12 +0000694 if (changed) {
Chris Lattner58f9f582010-11-21 00:28:59 +0000695 MD->removeInstruction(SI);
Owen Anderson18e4fed2010-10-15 22:52:12 +0000696 SI->eraseFromParent();
Chris Lattnercaf5c0d2011-01-09 19:26:10 +0000697 MD->removeInstruction(LI);
Owen Anderson18e4fed2010-10-15 22:52:12 +0000698 LI->eraseFromParent();
699 ++NumMemCpyInstr;
700 return true;
701 }
702 }
703 }
704 }
Nadav Rotem465834c2012-07-24 10:51:42 +0000705
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000706 // There are two cases that are interesting for this code to handle: memcpy
707 // and memset. Right now we only handle memset.
Nadav Rotem465834c2012-07-24 10:51:42 +0000708
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000709 // Ensure that the value being stored is something that can be memset'able a
710 // byte at a time like "0" or "-1" or any width, as well as things like
711 // 0xA0A0A0A0 and 0.0.
Amaury Sechet3235c082016-01-06 19:47:24 +0000712 auto *V = SI->getOperand(0);
713 if (Value *ByteVal = isBytewiseValue(V)) {
Chris Lattnerc6381472011-01-08 20:24:01 +0000714 if (Instruction *I = tryMergingIntoMemset(SI, SI->getPointerOperand(),
715 ByteVal)) {
Duncan P. N. Exon Smithbe4d8cb2015-10-13 19:26:58 +0000716 BBI = I->getIterator(); // Don't invalidate iterator.
Chris Lattnerc6381472011-01-08 20:24:01 +0000717 return true;
Mon P Wangc576ee92010-04-04 03:10:48 +0000718 }
Nadav Rotem465834c2012-07-24 10:51:42 +0000719
Amaury Sechet3235c082016-01-06 19:47:24 +0000720 // If we have an aggregate, we try to promote it to memset regardless
721 // of opportunity for merging as it can expose optimization opportunities
722 // in subsequent passes.
723 auto *T = V->getType();
724 if (T->isAggregateType()) {
725 uint64_t Size = DL.getTypeStoreSize(T);
726 unsigned Align = SI->getAlignment();
727 if (!Align)
728 Align = DL.getABITypeAlignment(T);
729 IRBuilder<> Builder(SI);
730 auto *M = Builder.CreateMemSet(SI->getPointerOperand(), ByteVal,
731 Size, Align, SI->isVolatile());
732
733 DEBUG(dbgs() << "Promoting " << *SI << " to " << *M << "\n");
734
735 MD->removeInstruction(SI);
736 SI->eraseFromParent();
737 NumMemSetInfer++;
738
739 // Make sure we do not invalidate the iterator.
740 BBI = M->getIterator();
741 return true;
742 }
743 }
744
Chris Lattnerc6381472011-01-08 20:24:01 +0000745 return false;
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000746}
747
Sean Silva6347df02016-06-14 02:44:55 +0000748bool MemCpyOptPass::processMemSet(MemSetInst *MSI, BasicBlock::iterator &BBI) {
Chris Lattner9a1d63b2011-01-08 21:19:19 +0000749 // See if there is another memset or store neighboring this memset which
750 // allows us to widen out the memset to do a single larger store.
Chris Lattnerff6ed2a2011-01-08 22:11:56 +0000751 if (isa<ConstantInt>(MSI->getLength()) && !MSI->isVolatile())
752 if (Instruction *I = tryMergingIntoMemset(MSI, MSI->getDest(),
753 MSI->getValue())) {
Duncan P. N. Exon Smithbe4d8cb2015-10-13 19:26:58 +0000754 BBI = I->getIterator(); // Don't invalidate iterator.
Chris Lattnerff6ed2a2011-01-08 22:11:56 +0000755 return true;
756 }
Chris Lattner9a1d63b2011-01-08 21:19:19 +0000757 return false;
758}
759
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000760
Sanjay Patela75c41e2015-08-13 22:53:20 +0000761/// Takes a memcpy and a call that it depends on,
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000762/// and checks for the possibility of a call slot optimization by having
763/// the call write its result directly into the destination of the memcpy.
Sean Silva6347df02016-06-14 02:44:55 +0000764bool MemCpyOptPass::performCallSlotOptzn(Instruction *cpy, Value *cpyDest,
765 Value *cpySrc, uint64_t cpyLen,
766 unsigned cpyAlign, CallInst *C) {
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000767 // The general transformation to keep in mind is
768 //
769 // call @func(..., src, ...)
770 // memcpy(dest, src, ...)
771 //
772 // ->
773 //
774 // memcpy(dest, src, ...)
775 // call @func(..., dest, ...)
776 //
777 // Since moving the memcpy is technically awkward, we additionally check that
778 // src only holds uninitialized values at the moment of the call, meaning that
779 // the memcpy can be discarded rather than moved.
780
Tim Shen7aa0ad62016-06-08 19:42:32 +0000781 // Lifetime marks shouldn't be operated on.
782 if (Function *F = C->getCalledFunction())
783 if (F->isIntrinsic() && F->getIntrinsicID() == Intrinsic::lifetime_start)
784 return false;
785
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000786 // Deliberately get the source and destination with bitcasts stripped away,
787 // because we'll need to do type comparisons based on the underlying type.
Gabor Greif62f0aac2010-07-28 22:50:26 +0000788 CallSite CS(C);
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000789
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000790 // Require that src be an alloca. This simplifies the reasoning considerably.
Chris Lattnerb5557a72009-09-01 17:09:55 +0000791 AllocaInst *srcAlloca = dyn_cast<AllocaInst>(cpySrc);
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000792 if (!srcAlloca)
793 return false;
794
Chris Lattnerb5557a72009-09-01 17:09:55 +0000795 ConstantInt *srcArraySize = dyn_cast<ConstantInt>(srcAlloca->getArraySize());
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000796 if (!srcArraySize)
797 return false;
798
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000799 const DataLayout &DL = cpy->getModule()->getDataLayout();
800 uint64_t srcSize = DL.getTypeAllocSize(srcAlloca->getAllocatedType()) *
801 srcArraySize->getZExtValue();
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000802
Owen Anderson18e4fed2010-10-15 22:52:12 +0000803 if (cpyLen < srcSize)
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000804 return false;
805
806 // Check that accessing the first srcSize bytes of dest will not cause a
807 // trap. Otherwise the transform is invalid since it might cause a trap
808 // to occur earlier than it otherwise would.
Chris Lattnerb5557a72009-09-01 17:09:55 +0000809 if (AllocaInst *A = dyn_cast<AllocaInst>(cpyDest)) {
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000810 // The destination is an alloca. Check it is larger than srcSize.
Chris Lattnerb5557a72009-09-01 17:09:55 +0000811 ConstantInt *destArraySize = dyn_cast<ConstantInt>(A->getArraySize());
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000812 if (!destArraySize)
813 return false;
814
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000815 uint64_t destSize = DL.getTypeAllocSize(A->getAllocatedType()) *
816 destArraySize->getZExtValue();
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000817
818 if (destSize < srcSize)
819 return false;
Chris Lattnerb5557a72009-09-01 17:09:55 +0000820 } else if (Argument *A = dyn_cast<Argument>(cpyDest)) {
David Majnemerd99068d2016-05-26 19:24:24 +0000821 // The store to dest may never happen if the call can throw.
822 if (C->mayThrow())
823 return false;
824
Bjorn Steinbrinkd20816f2014-10-16 19:43:08 +0000825 if (A->getDereferenceableBytes() < srcSize) {
826 // If the destination is an sret parameter then only accesses that are
827 // outside of the returned struct type can trap.
828 if (!A->hasStructRetAttr())
829 return false;
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000830
Bjorn Steinbrinkd20816f2014-10-16 19:43:08 +0000831 Type *StructTy = cast<PointerType>(A->getType())->getElementType();
832 if (!StructTy->isSized()) {
833 // The call may never return and hence the copy-instruction may never
834 // be executed, and therefore it's not safe to say "the destination
835 // has at least <cpyLen> bytes, as implied by the copy-instruction",
836 return false;
837 }
838
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000839 uint64_t destSize = DL.getTypeAllocSize(StructTy);
Bjorn Steinbrinkd20816f2014-10-16 19:43:08 +0000840 if (destSize < srcSize)
841 return false;
Shuxin Yang140d5922013-06-08 04:56:05 +0000842 }
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000843 } else {
844 return false;
845 }
846
Duncan Sands933db772012-10-05 07:29:46 +0000847 // Check that dest points to memory that is at least as aligned as src.
848 unsigned srcAlign = srcAlloca->getAlignment();
849 if (!srcAlign)
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000850 srcAlign = DL.getABITypeAlignment(srcAlloca->getAllocatedType());
Duncan Sands933db772012-10-05 07:29:46 +0000851 bool isDestSufficientlyAligned = srcAlign <= cpyAlign;
852 // If dest is not aligned enough and we can't increase its alignment then
853 // bail out.
854 if (!isDestSufficientlyAligned && !isa<AllocaInst>(cpyDest))
855 return false;
856
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000857 // Check that src is not accessed except via the call and the memcpy. This
858 // guarantees that it holds only undefined values when passed in (so the final
859 // memcpy can be dropped), that it is not read or written between the call and
860 // the memcpy, and that writing beyond the end of it is undefined.
Chandler Carruthcdf47882014-03-09 03:16:01 +0000861 SmallVector<User*, 8> srcUseList(srcAlloca->user_begin(),
862 srcAlloca->user_end());
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000863 while (!srcUseList.empty()) {
Chandler Carruthcdf47882014-03-09 03:16:01 +0000864 User *U = srcUseList.pop_back_val();
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000865
Chandler Carruthcdf47882014-03-09 03:16:01 +0000866 if (isa<BitCastInst>(U) || isa<AddrSpaceCastInst>(U)) {
867 for (User *UU : U->users())
868 srcUseList.push_back(UU);
Chandler Carruth18cee1d2014-09-01 10:09:18 +0000869 continue;
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000870 }
Chandler Carruth18cee1d2014-09-01 10:09:18 +0000871 if (GetElementPtrInst *G = dyn_cast<GetElementPtrInst>(U)) {
872 if (!G->hasAllZeroIndices())
873 return false;
874
875 for (User *UU : U->users())
876 srcUseList.push_back(UU);
877 continue;
878 }
879 if (const IntrinsicInst *IT = dyn_cast<IntrinsicInst>(U))
880 if (IT->getIntrinsicID() == Intrinsic::lifetime_start ||
881 IT->getIntrinsicID() == Intrinsic::lifetime_end)
882 continue;
883
884 if (U != C && U != cpy)
885 return false;
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000886 }
887
Nick Lewycky703e4882014-07-14 18:52:02 +0000888 // Check that src isn't captured by the called function since the
889 // transformation can cause aliasing issues in that case.
890 for (unsigned i = 0, e = CS.arg_size(); i != e; ++i)
891 if (CS.getArgument(i) == cpySrc && !CS.doesNotCapture(i))
892 return false;
893
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000894 // Since we're changing the parameter to the callsite, we need to make sure
895 // that what would be the new parameter dominates the callsite.
Sean Silva6347df02016-06-14 02:44:55 +0000896 DominatorTree &DT = LookupDomTree();
Chris Lattnerb5557a72009-09-01 17:09:55 +0000897 if (Instruction *cpyDestInst = dyn_cast<Instruction>(cpyDest))
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000898 if (!DT.dominates(cpyDestInst, C))
899 return false;
900
901 // In addition to knowing that the call does not access src in some
902 // unexpected manner, for example via a global, which we deduce from
903 // the use analysis, we also need to know that it does not sneakily
904 // access dest. We rely on AA to figure this out for us.
Sean Silva6347df02016-06-14 02:44:55 +0000905 AliasAnalysis &AA = LookupAliasAnalysis();
Chandler Carruth194f59c2015-07-22 23:15:57 +0000906 ModRefInfo MR = AA.getModRefInfo(C, cpyDest, srcSize);
Chad Rosiera968caf2012-05-14 20:35:04 +0000907 // If necessary, perform additional analysis.
Chandler Carruth194f59c2015-07-22 23:15:57 +0000908 if (MR != MRI_NoModRef)
Chad Rosiera968caf2012-05-14 20:35:04 +0000909 MR = AA.callCapturesBefore(C, cpyDest, srcSize, &DT);
Chandler Carruth194f59c2015-07-22 23:15:57 +0000910 if (MR != MRI_NoModRef)
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000911 return false;
912
913 // All the checks have passed, so do the transformation.
Owen Andersond071a872008-06-01 21:52:16 +0000914 bool changedArgument = false;
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000915 for (unsigned i = 0; i < CS.arg_size(); ++i)
Owen Anderson38099c12008-06-01 22:26:26 +0000916 if (CS.getArgument(i)->stripPointerCasts() == cpySrc) {
Duncan Sandsa6d20012012-10-04 13:53:21 +0000917 Value *Dest = cpySrc->getType() == cpyDest->getType() ? cpyDest
918 : CastInst::CreatePointerCast(cpyDest, cpySrc->getType(),
919 cpyDest->getName(), C);
Owen Andersond071a872008-06-01 21:52:16 +0000920 changedArgument = true;
Duncan Sandsa6d20012012-10-04 13:53:21 +0000921 if (CS.getArgument(i)->getType() == Dest->getType())
922 CS.setArgument(i, Dest);
Chris Lattnerb5557a72009-09-01 17:09:55 +0000923 else
Duncan Sandsa6d20012012-10-04 13:53:21 +0000924 CS.setArgument(i, CastInst::CreatePointerCast(Dest,
925 CS.getArgument(i)->getType(), Dest->getName(), C));
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000926 }
927
Owen Andersond071a872008-06-01 21:52:16 +0000928 if (!changedArgument)
929 return false;
930
Duncan Sandsc6ada692012-10-04 10:54:40 +0000931 // If the destination wasn't sufficiently aligned then increase its alignment.
932 if (!isDestSufficientlyAligned) {
933 assert(isa<AllocaInst>(cpyDest) && "Can only increase alloca alignment!");
934 cast<AllocaInst>(cpyDest)->setAlignment(srcAlign);
935 }
936
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000937 // Drop any cached information about the call, because we may have changed
938 // its dependence information by changing its parameter.
Chris Lattner58f9f582010-11-21 00:28:59 +0000939 MD->removeInstruction(C);
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000940
Bjorn Steinbrink71bf3b82015-02-07 17:54:36 +0000941 // Update AA metadata
942 // FIXME: MD_tbaa_struct and MD_mem_parallel_loop_access should also be
943 // handled here, but combineMetadata doesn't support them yet
Piotr Padlewskidc9b2cf2015-10-02 22:12:22 +0000944 unsigned KnownIDs[] = {LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope,
945 LLVMContext::MD_noalias,
946 LLVMContext::MD_invariant_group};
Bjorn Steinbrink71bf3b82015-02-07 17:54:36 +0000947 combineMetadata(C, cpy, KnownIDs);
948
Chris Lattner58f9f582010-11-21 00:28:59 +0000949 // Remove the memcpy.
950 MD->removeInstruction(cpy);
Dan Gohmand2d1ae12010-06-22 15:08:57 +0000951 ++NumMemCpyInstr;
Owen Andersonef9a6fd2008-04-09 08:23:16 +0000952
953 return true;
954}
955
Sanjay Patela75c41e2015-08-13 22:53:20 +0000956/// We've found that the (upward scanning) memory dependence of memcpy 'M' is
957/// the memcpy 'MDep'. Try to simplify M to copy from MDep's input if we can.
Sean Silva6347df02016-06-14 02:44:55 +0000958bool MemCpyOptPass::processMemCpyMemCpyDependence(MemCpyInst *M,
959 MemCpyInst *MDep) {
Chris Lattner7e9b2ea2010-11-18 07:02:37 +0000960 // We can only transforms memcpy's where the dest of one is the source of the
961 // other.
Chris Lattner58f9f582010-11-21 00:28:59 +0000962 if (M->getSource() != MDep->getDest() || MDep->isVolatile())
Chris Lattner7e9b2ea2010-11-18 07:02:37 +0000963 return false;
Nadav Rotem465834c2012-07-24 10:51:42 +0000964
Chris Lattnerfd51c522010-12-09 07:39:50 +0000965 // If dep instruction is reading from our current input, then it is a noop
966 // transfer and substituting the input won't change this instruction. Just
967 // ignore the input and let someone else zap MDep. This handles cases like:
968 // memcpy(a <- a)
969 // memcpy(b <- a)
970 if (M->getSource() == MDep->getSource())
971 return false;
Nadav Rotem465834c2012-07-24 10:51:42 +0000972
Chris Lattner0ab5e2c2011-04-15 05:18:47 +0000973 // Second, the length of the memcpy's must be the same, or the preceding one
Chris Lattner7e9b2ea2010-11-18 07:02:37 +0000974 // must be larger than the following one.
Dan Gohman19e30d52011-01-21 22:07:57 +0000975 ConstantInt *MDepLen = dyn_cast<ConstantInt>(MDep->getLength());
976 ConstantInt *MLen = dyn_cast<ConstantInt>(M->getLength());
977 if (!MDepLen || !MLen || MDepLen->getZExtValue() < MLen->getZExtValue())
978 return false;
Nadav Rotem465834c2012-07-24 10:51:42 +0000979
Sean Silva6347df02016-06-14 02:44:55 +0000980 AliasAnalysis &AA = LookupAliasAnalysis();
Chris Lattner59572292010-11-21 08:06:10 +0000981
982 // Verify that the copied-from memory doesn't change in between the two
983 // transfers. For example, in:
984 // memcpy(a <- b)
985 // *b = 42;
986 // memcpy(c <- a)
987 // It would be invalid to transform the second memcpy into memcpy(c <- b).
988 //
989 // TODO: If the code between M and MDep is transparent to the destination "c",
990 // then we could still perform the xform by moving M up to the first memcpy.
991 //
992 // NOTE: This is conservative, it will stop on any read from the source loc,
993 // not just the defining memcpy.
Duncan P. N. Exon Smithbe4d8cb2015-10-13 19:26:58 +0000994 MemDepResult SourceDep =
995 MD->getPointerDependencyFrom(MemoryLocation::getForSource(MDep), false,
996 M->getIterator(), M->getParent());
Chris Lattner59572292010-11-21 08:06:10 +0000997 if (!SourceDep.isClobber() || SourceDep.getInst() != MDep)
998 return false;
Nadav Rotem465834c2012-07-24 10:51:42 +0000999
Chris Lattner731caac2010-11-18 08:00:57 +00001000 // If the dest of the second might alias the source of the first, then the
1001 // source and dest might overlap. We still want to eliminate the intermediate
1002 // value, but we have to generate a memmove instead of memcpy.
Chris Lattner6cf8d6c2010-12-26 22:57:41 +00001003 bool UseMemMove = false;
Chandler Carruth70c61c12015-06-04 02:03:15 +00001004 if (!AA.isNoAlias(MemoryLocation::getForDest(M),
1005 MemoryLocation::getForSource(MDep)))
Chris Lattner6cf8d6c2010-12-26 22:57:41 +00001006 UseMemMove = true;
Nadav Rotem465834c2012-07-24 10:51:42 +00001007
Chris Lattner58f9f582010-11-21 00:28:59 +00001008 // If all checks passed, then we can transform M.
Nadav Rotem465834c2012-07-24 10:51:42 +00001009
Pete Cooper67cf9a72015-11-19 05:56:52 +00001010 // Make sure to use the lesser of the alignment of the source and the dest
1011 // since we're changing where we're reading from, but don't want to increase
1012 // the alignment past what can be read from or written to.
Chris Lattner7e9b2ea2010-11-18 07:02:37 +00001013 // TODO: Is this worth it if we're creating a less aligned memcpy? For
1014 // example we could be moving from movaps -> movq on x86.
Pete Cooper67cf9a72015-11-19 05:56:52 +00001015 unsigned Align = std::min(MDep->getAlignment(), M->getAlignment());
1016
Chris Lattner6cf8d6c2010-12-26 22:57:41 +00001017 IRBuilder<> Builder(M);
1018 if (UseMemMove)
1019 Builder.CreateMemMove(M->getRawDest(), MDep->getRawSource(), M->getLength(),
Pete Cooper67cf9a72015-11-19 05:56:52 +00001020 Align, M->isVolatile());
Chris Lattner6cf8d6c2010-12-26 22:57:41 +00001021 else
1022 Builder.CreateMemCpy(M->getRawDest(), MDep->getRawSource(), M->getLength(),
Pete Cooper67cf9a72015-11-19 05:56:52 +00001023 Align, M->isVolatile());
Chris Lattner1385dff2010-11-18 08:07:09 +00001024
Chris Lattner59572292010-11-21 08:06:10 +00001025 // Remove the instruction we're replacing.
Chris Lattner58f9f582010-11-21 00:28:59 +00001026 MD->removeInstruction(M);
Chris Lattner1385dff2010-11-18 08:07:09 +00001027 M->eraseFromParent();
1028 ++NumMemCpyInstr;
1029 return true;
Chris Lattner7e9b2ea2010-11-18 07:02:37 +00001030}
1031
Ahmed Bougacha83f78a42015-04-17 22:20:57 +00001032/// We've found that the (upward scanning) memory dependence of \p MemCpy is
1033/// \p MemSet. Try to simplify \p MemSet to only set the trailing bytes that
1034/// weren't copied over by \p MemCpy.
1035///
1036/// In other words, transform:
1037/// \code
1038/// memset(dst, c, dst_size);
1039/// memcpy(dst, src, src_size);
1040/// \endcode
1041/// into:
1042/// \code
1043/// memcpy(dst, src, src_size);
1044/// memset(dst + src_size, c, dst_size <= src_size ? 0 : dst_size - src_size);
1045/// \endcode
Sean Silva6347df02016-06-14 02:44:55 +00001046bool MemCpyOptPass::processMemSetMemCpyDependence(MemCpyInst *MemCpy,
1047 MemSetInst *MemSet) {
Ahmed Bougacha83f78a42015-04-17 22:20:57 +00001048 // We can only transform memset/memcpy with the same destination.
1049 if (MemSet->getDest() != MemCpy->getDest())
1050 return false;
1051
Ahmed Bougacha97876fa2015-05-21 01:43:39 +00001052 // Check that there are no other dependencies on the memset destination.
Duncan P. N. Exon Smithbe4d8cb2015-10-13 19:26:58 +00001053 MemDepResult DstDepInfo =
1054 MD->getPointerDependencyFrom(MemoryLocation::getForDest(MemSet), false,
1055 MemCpy->getIterator(), MemCpy->getParent());
Ahmed Bougacha97876fa2015-05-21 01:43:39 +00001056 if (DstDepInfo.getInst() != MemSet)
1057 return false;
1058
Ahmed Bougacha9692e302015-04-21 21:28:33 +00001059 // Use the same i8* dest as the memcpy, killing the memset dest if different.
1060 Value *Dest = MemCpy->getRawDest();
Ahmed Bougacha83f78a42015-04-17 22:20:57 +00001061 Value *DestSize = MemSet->getLength();
1062 Value *SrcSize = MemCpy->getLength();
1063
1064 // By default, create an unaligned memset.
1065 unsigned Align = 1;
1066 // If Dest is aligned, and SrcSize is constant, use the minimum alignment
1067 // of the sum.
1068 const unsigned DestAlign =
Pete Cooper67cf9a72015-11-19 05:56:52 +00001069 std::max(MemSet->getAlignment(), MemCpy->getAlignment());
Ahmed Bougacha83f78a42015-04-17 22:20:57 +00001070 if (DestAlign > 1)
1071 if (ConstantInt *SrcSizeC = dyn_cast<ConstantInt>(SrcSize))
1072 Align = MinAlign(SrcSizeC->getZExtValue(), DestAlign);
1073
Ahmed Bougacha97876fa2015-05-21 01:43:39 +00001074 IRBuilder<> Builder(MemCpy);
Ahmed Bougacha83f78a42015-04-17 22:20:57 +00001075
Ahmed Bougacha05b72c12015-04-18 23:06:04 +00001076 // If the sizes have different types, zext the smaller one.
Ahmed Bougacha7216ccc2015-04-18 17:57:41 +00001077 if (DestSize->getType() != SrcSize->getType()) {
Ahmed Bougacha05b72c12015-04-18 23:06:04 +00001078 if (DestSize->getType()->getIntegerBitWidth() >
1079 SrcSize->getType()->getIntegerBitWidth())
1080 SrcSize = Builder.CreateZExt(SrcSize, DestSize->getType());
1081 else
1082 DestSize = Builder.CreateZExt(DestSize, SrcSize->getType());
Ahmed Bougacha7216ccc2015-04-18 17:57:41 +00001083 }
1084
Ahmed Bougacha83f78a42015-04-17 22:20:57 +00001085 Value *MemsetLen =
1086 Builder.CreateSelect(Builder.CreateICmpULE(DestSize, SrcSize),
1087 ConstantInt::getNullValue(DestSize->getType()),
1088 Builder.CreateSub(DestSize, SrcSize));
1089 Builder.CreateMemSet(Builder.CreateGEP(Dest, SrcSize), MemSet->getOperand(1),
1090 MemsetLen, Align);
1091
1092 MD->removeInstruction(MemSet);
1093 MemSet->eraseFromParent();
1094 return true;
1095}
Chris Lattner7e9b2ea2010-11-18 07:02:37 +00001096
Ahmed Bougachaf8fa3b82015-05-16 01:32:26 +00001097/// Transform memcpy to memset when its source was just memset.
1098/// In other words, turn:
1099/// \code
1100/// memset(dst1, c, dst1_size);
1101/// memcpy(dst2, dst1, dst2_size);
1102/// \endcode
1103/// into:
1104/// \code
1105/// memset(dst1, c, dst1_size);
1106/// memset(dst2, c, dst2_size);
1107/// \endcode
1108/// When dst2_size <= dst1_size.
1109///
1110/// The \p MemCpy must have a Constant length.
Sean Silva6347df02016-06-14 02:44:55 +00001111bool MemCpyOptPass::performMemCpyToMemSetOptzn(MemCpyInst *MemCpy,
1112 MemSetInst *MemSet) {
Ahmed Bougachaf8fa3b82015-05-16 01:32:26 +00001113 // This only makes sense on memcpy(..., memset(...), ...).
1114 if (MemSet->getRawDest() != MemCpy->getRawSource())
1115 return false;
1116
1117 ConstantInt *CopySize = cast<ConstantInt>(MemCpy->getLength());
1118 ConstantInt *MemSetSize = dyn_cast<ConstantInt>(MemSet->getLength());
1119 // Make sure the memcpy doesn't read any more than what the memset wrote.
1120 // Don't worry about sizes larger than i64.
1121 if (!MemSetSize || CopySize->getZExtValue() > MemSetSize->getZExtValue())
1122 return false;
1123
Ahmed Bougacha0541c672015-05-21 00:08:35 +00001124 IRBuilder<> Builder(MemCpy);
Ahmed Bougachaf8fa3b82015-05-16 01:32:26 +00001125 Builder.CreateMemSet(MemCpy->getRawDest(), MemSet->getOperand(1),
Pete Cooper67cf9a72015-11-19 05:56:52 +00001126 CopySize, MemCpy->getAlignment());
Ahmed Bougachaf8fa3b82015-05-16 01:32:26 +00001127 return true;
1128}
1129
Sanjay Patela75c41e2015-08-13 22:53:20 +00001130/// Perform simplification of memcpy's. If we have memcpy A
Gabor Greif62f0aac2010-07-28 22:50:26 +00001131/// which copies X to Y, and memcpy B which copies Y to Z, then we can rewrite
1132/// B to be a memcpy from X to Z (or potentially a memmove, depending on
1133/// circumstances). This allows later passes to remove the first memcpy
1134/// altogether.
Sean Silva6347df02016-06-14 02:44:55 +00001135bool MemCpyOptPass::processMemCpy(MemCpyInst *M) {
Nick Lewycky00703e72014-02-04 00:18:54 +00001136 // We can only optimize non-volatile memcpy's.
1137 if (M->isVolatile()) return false;
Owen Anderson18e4fed2010-10-15 22:52:12 +00001138
Chris Lattnerbc4457e2010-12-09 07:45:45 +00001139 // If the source and destination of the memcpy are the same, then zap it.
1140 if (M->getSource() == M->getDest()) {
1141 MD->removeInstruction(M);
1142 M->eraseFromParent();
1143 return false;
1144 }
Benjamin Kramerea9152e2010-12-24 21:17:12 +00001145
1146 // If copying from a constant, try to turn the memcpy into a memset.
Benjamin Kramerb90b2f02010-12-24 22:23:59 +00001147 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(M->getSource()))
Benjamin Kramer30342fb2010-12-26 15:23:45 +00001148 if (GV->isConstant() && GV->hasDefinitiveInitializer())
Benjamin Kramerb90b2f02010-12-24 22:23:59 +00001149 if (Value *ByteVal = isBytewiseValue(GV->getInitializer())) {
Chris Lattner6cf8d6c2010-12-26 22:57:41 +00001150 IRBuilder<> Builder(M);
Nick Lewycky00703e72014-02-04 00:18:54 +00001151 Builder.CreateMemSet(M->getRawDest(), ByteVal, M->getLength(),
Pete Cooper67cf9a72015-11-19 05:56:52 +00001152 M->getAlignment(), false);
Benjamin Kramerb90b2f02010-12-24 22:23:59 +00001153 MD->removeInstruction(M);
1154 M->eraseFromParent();
1155 ++NumCpyToSet;
1156 return true;
1157 }
Benjamin Kramerea9152e2010-12-24 21:17:12 +00001158
Ahmed Bougachab6169662015-05-11 23:09:46 +00001159 MemDepResult DepInfo = MD->getDependency(M);
Ahmed Bougacha83f78a42015-04-17 22:20:57 +00001160
1161 // Try to turn a partially redundant memset + memcpy into
1162 // memcpy + smaller memset. We don't need the memcpy size for this.
Ahmed Bougachab6169662015-05-11 23:09:46 +00001163 if (DepInfo.isClobber())
1164 if (MemSetInst *MDep = dyn_cast<MemSetInst>(DepInfo.getInst()))
Ahmed Bougacha83f78a42015-04-17 22:20:57 +00001165 if (processMemSetMemCpyDependence(M, MDep))
1166 return true;
1167
Nick Lewycky00703e72014-02-04 00:18:54 +00001168 // The optimizations after this point require the memcpy size.
1169 ConstantInt *CopySize = dyn_cast<ConstantInt>(M->getLength());
Craig Topperf40110f2014-04-25 05:29:35 +00001170 if (!CopySize) return false;
Nick Lewycky00703e72014-02-04 00:18:54 +00001171
Ahmed Bougachaf8fa3b82015-05-16 01:32:26 +00001172 // There are four possible optimizations we can do for memcpy:
Chris Lattnerb5557a72009-09-01 17:09:55 +00001173 // a) memcpy-memcpy xform which exposes redundance for DSE.
1174 // b) call-memcpy xform for return slot optimization.
Nick Lewycky77d5fb42014-03-26 23:45:15 +00001175 // c) memcpy from freshly alloca'd space or space that has just started its
1176 // lifetime copies undefined data, and we can therefore eliminate the
1177 // memcpy in favor of the data that was already at the destination.
Ahmed Bougachaf8fa3b82015-05-16 01:32:26 +00001178 // d) memcpy from a just-memset'd source can be turned into memset.
Nick Lewycky0a7e9cc2011-10-16 20:13:32 +00001179 if (DepInfo.isClobber()) {
1180 if (CallInst *C = dyn_cast<CallInst>(DepInfo.getInst())) {
1181 if (performCallSlotOptzn(M, M->getDest(), M->getSource(),
Pete Cooper67cf9a72015-11-19 05:56:52 +00001182 CopySize->getZExtValue(), M->getAlignment(),
Duncan Sandsc6ada692012-10-04 10:54:40 +00001183 C)) {
Nick Lewycky0a7e9cc2011-10-16 20:13:32 +00001184 MD->removeInstruction(M);
1185 M->eraseFromParent();
1186 return true;
1187 }
Chris Lattnerbc4457e2010-12-09 07:45:45 +00001188 }
Owen Andersonef9a6fd2008-04-09 08:23:16 +00001189 }
Ahmed Charles32e983e2012-02-13 06:30:56 +00001190
Chandler Carruthac80dc72015-06-17 07:18:54 +00001191 MemoryLocation SrcLoc = MemoryLocation::getForSource(M);
Duncan P. N. Exon Smithbe4d8cb2015-10-13 19:26:58 +00001192 MemDepResult SrcDepInfo = MD->getPointerDependencyFrom(
1193 SrcLoc, true, M->getIterator(), M->getParent());
Ahmed Bougachab6169662015-05-11 23:09:46 +00001194
Nick Lewycky0a7e9cc2011-10-16 20:13:32 +00001195 if (SrcDepInfo.isClobber()) {
1196 if (MemCpyInst *MDep = dyn_cast<MemCpyInst>(SrcDepInfo.getInst()))
Ahmed Bougacha15a31f62015-05-16 01:23:47 +00001197 return processMemCpyMemCpyDependence(M, MDep);
Nick Lewycky99384942014-02-06 06:29:19 +00001198 } else if (SrcDepInfo.isDef()) {
Nick Lewycky77d5fb42014-03-26 23:45:15 +00001199 Instruction *I = SrcDepInfo.getInst();
1200 bool hasUndefContents = false;
1201
1202 if (isa<AllocaInst>(I)) {
1203 hasUndefContents = true;
1204 } else if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
1205 if (II->getIntrinsicID() == Intrinsic::lifetime_start)
1206 if (ConstantInt *LTSize = dyn_cast<ConstantInt>(II->getArgOperand(0)))
1207 if (LTSize->getZExtValue() >= CopySize->getZExtValue())
1208 hasUndefContents = true;
1209 }
1210
1211 if (hasUndefContents) {
Nick Lewycky99384942014-02-06 06:29:19 +00001212 MD->removeInstruction(M);
1213 M->eraseFromParent();
1214 ++NumMemCpyInstr;
1215 return true;
1216 }
Nick Lewycky0a7e9cc2011-10-16 20:13:32 +00001217 }
1218
Ahmed Bougachaf8fa3b82015-05-16 01:32:26 +00001219 if (SrcDepInfo.isClobber())
1220 if (MemSetInst *MDep = dyn_cast<MemSetInst>(SrcDepInfo.getInst()))
1221 if (performMemCpyToMemSetOptzn(M, MDep)) {
1222 MD->removeInstruction(M);
1223 M->eraseFromParent();
1224 ++NumCpyToSet;
1225 return true;
1226 }
1227
Owen Andersonad5367f2008-04-29 21:51:00 +00001228 return false;
Owen Andersonef9a6fd2008-04-09 08:23:16 +00001229}
1230
Sanjay Patela75c41e2015-08-13 22:53:20 +00001231/// Transforms memmove calls to memcpy calls when the src/dst are guaranteed
1232/// not to alias.
Sean Silva6347df02016-06-14 02:44:55 +00001233bool MemCpyOptPass::processMemMove(MemMoveInst *M) {
1234 AliasAnalysis &AA = LookupAliasAnalysis();
Chris Lattner1145e332009-09-01 17:56:32 +00001235
Chris Lattner23f61a02011-05-01 18:27:11 +00001236 if (!TLI->has(LibFunc::memmove))
1237 return false;
Nadav Rotem465834c2012-07-24 10:51:42 +00001238
Chris Lattner1145e332009-09-01 17:56:32 +00001239 // See if the pointers alias.
Chandler Carruth70c61c12015-06-04 02:03:15 +00001240 if (!AA.isNoAlias(MemoryLocation::getForDest(M),
1241 MemoryLocation::getForSource(M)))
Chris Lattner1145e332009-09-01 17:56:32 +00001242 return false;
Nadav Rotem465834c2012-07-24 10:51:42 +00001243
Sean Silva6347df02016-06-14 02:44:55 +00001244 DEBUG(dbgs() << "MemCpyOptPass: Optimizing memmove -> memcpy: " << *M
1245 << "\n");
Nadav Rotem465834c2012-07-24 10:51:42 +00001246
Chris Lattner1145e332009-09-01 17:56:32 +00001247 // If not, then we know we can transform this.
Jay Foadb804a2b2011-07-12 14:06:48 +00001248 Type *ArgTys[3] = { M->getRawDest()->getType(),
1249 M->getRawSource()->getType(),
1250 M->getLength()->getType() };
Sanjay Patelaf674fb2015-12-14 17:24:23 +00001251 M->setCalledFunction(Intrinsic::getDeclaration(M->getModule(),
1252 Intrinsic::memcpy, ArgTys));
Duncan Sands0edc7102009-09-03 13:37:16 +00001253
Chris Lattner1145e332009-09-01 17:56:32 +00001254 // MemDep may have over conservative information about this instruction, just
1255 // conservatively flush it from the cache.
Chris Lattner58f9f582010-11-21 00:28:59 +00001256 MD->removeInstruction(M);
Duncan Sands0edc7102009-09-03 13:37:16 +00001257
1258 ++NumMoveToCpy;
Chris Lattner1145e332009-09-01 17:56:32 +00001259 return true;
1260}
Nadav Rotem465834c2012-07-24 10:51:42 +00001261
Sanjay Patela75c41e2015-08-13 22:53:20 +00001262/// This is called on every byval argument in call sites.
Sean Silva6347df02016-06-14 02:44:55 +00001263bool MemCpyOptPass::processByValArgument(CallSite CS, unsigned ArgNo) {
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001264 const DataLayout &DL = CS.getCaller()->getParent()->getDataLayout();
Chris Lattner59572292010-11-21 08:06:10 +00001265 // Find out what feeds this byval argument.
Chris Lattner58f9f582010-11-21 00:28:59 +00001266 Value *ByValArg = CS.getArgument(ArgNo);
Nick Lewyckyc585de62011-10-12 00:14:31 +00001267 Type *ByValTy = cast<PointerType>(ByValArg->getType())->getElementType();
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001268 uint64_t ByValSize = DL.getTypeAllocSize(ByValTy);
Chandler Carruthac80dc72015-06-17 07:18:54 +00001269 MemDepResult DepInfo = MD->getPointerDependencyFrom(
Duncan P. N. Exon Smithbe4d8cb2015-10-13 19:26:58 +00001270 MemoryLocation(ByValArg, ByValSize), true,
1271 CS.getInstruction()->getIterator(), CS.getInstruction()->getParent());
Chris Lattner58f9f582010-11-21 00:28:59 +00001272 if (!DepInfo.isClobber())
1273 return false;
1274
1275 // If the byval argument isn't fed by a memcpy, ignore it. If it is fed by
1276 // a memcpy, see if we can byval from the source of the memcpy instead of the
1277 // result.
1278 MemCpyInst *MDep = dyn_cast<MemCpyInst>(DepInfo.getInst());
Craig Topperf40110f2014-04-25 05:29:35 +00001279 if (!MDep || MDep->isVolatile() ||
Chris Lattner58f9f582010-11-21 00:28:59 +00001280 ByValArg->stripPointerCasts() != MDep->getDest())
1281 return false;
Nadav Rotem465834c2012-07-24 10:51:42 +00001282
Chris Lattner58f9f582010-11-21 00:28:59 +00001283 // The length of the memcpy must be larger or equal to the size of the byval.
Chris Lattner58f9f582010-11-21 00:28:59 +00001284 ConstantInt *C1 = dyn_cast<ConstantInt>(MDep->getLength());
Craig Topperf40110f2014-04-25 05:29:35 +00001285 if (!C1 || C1->getValue().getZExtValue() < ByValSize)
Chris Lattner58f9f582010-11-21 00:28:59 +00001286 return false;
1287
Chris Lattner83791ce2011-05-23 00:03:39 +00001288 // Get the alignment of the byval. If the call doesn't specify the alignment,
1289 // then it is some target specific value that we can't know.
Chris Lattner58f9f582010-11-21 00:28:59 +00001290 unsigned ByValAlign = CS.getParamAlignment(ArgNo+1);
Chris Lattner83791ce2011-05-23 00:03:39 +00001291 if (ByValAlign == 0) return false;
Nadav Rotem465834c2012-07-24 10:51:42 +00001292
Chris Lattner83791ce2011-05-23 00:03:39 +00001293 // If it is greater than the memcpy, then we check to see if we can force the
1294 // source of the memcpy to the alignment we need. If we fail, we bail out.
Sean Silva6347df02016-06-14 02:44:55 +00001295 AssumptionCache &AC = LookupAssumptionCache();
1296 DominatorTree &DT = LookupDomTree();
Pete Cooper67cf9a72015-11-19 05:56:52 +00001297 if (MDep->getAlignment() < ByValAlign &&
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001298 getOrEnforceKnownAlignment(MDep->getSource(), ByValAlign, DL,
1299 CS.getInstruction(), &AC, &DT) < ByValAlign)
Chris Lattner83791ce2011-05-23 00:03:39 +00001300 return false;
Nadav Rotem465834c2012-07-24 10:51:42 +00001301
Chris Lattner58f9f582010-11-21 00:28:59 +00001302 // Verify that the copied-from memory doesn't change in between the memcpy and
1303 // the byval call.
1304 // memcpy(a <- b)
1305 // *b = 42;
1306 // foo(*a)
1307 // It would be invalid to transform the second memcpy into foo(*b).
Chris Lattner59572292010-11-21 08:06:10 +00001308 //
1309 // NOTE: This is conservative, it will stop on any read from the source loc,
1310 // not just the defining memcpy.
Duncan P. N. Exon Smithbe4d8cb2015-10-13 19:26:58 +00001311 MemDepResult SourceDep = MD->getPointerDependencyFrom(
1312 MemoryLocation::getForSource(MDep), false,
1313 CS.getInstruction()->getIterator(), MDep->getParent());
Chris Lattner59572292010-11-21 08:06:10 +00001314 if (!SourceDep.isClobber() || SourceDep.getInst() != MDep)
1315 return false;
Nadav Rotem465834c2012-07-24 10:51:42 +00001316
Chris Lattner58f9f582010-11-21 00:28:59 +00001317 Value *TmpCast = MDep->getSource();
1318 if (MDep->getSource()->getType() != ByValArg->getType())
1319 TmpCast = new BitCastInst(MDep->getSource(), ByValArg->getType(),
1320 "tmpcast", CS.getInstruction());
Nadav Rotem465834c2012-07-24 10:51:42 +00001321
Sean Silva6347df02016-06-14 02:44:55 +00001322 DEBUG(dbgs() << "MemCpyOptPass: Forwarding memcpy to byval:\n"
Chris Lattner58f9f582010-11-21 00:28:59 +00001323 << " " << *MDep << "\n"
1324 << " " << *CS.getInstruction() << "\n");
Nadav Rotem465834c2012-07-24 10:51:42 +00001325
Chris Lattner58f9f582010-11-21 00:28:59 +00001326 // Otherwise we're good! Update the byval argument.
1327 CS.setArgument(ArgNo, TmpCast);
1328 ++NumMemCpyInstr;
1329 return true;
1330}
1331
Sean Silva6347df02016-06-14 02:44:55 +00001332/// Executes one iteration of MemCpyOptPass.
1333bool MemCpyOptPass::iterateOnFunction(Function &F) {
Chris Lattnerb5557a72009-09-01 17:09:55 +00001334 bool MadeChange = false;
Owen Andersonef9a6fd2008-04-09 08:23:16 +00001335
Chris Lattnerb5557a72009-09-01 17:09:55 +00001336 // Walk all instruction in the function.
Benjamin Kramer135f7352016-06-26 12:28:59 +00001337 for (BasicBlock &BB : F) {
1338 for (BasicBlock::iterator BI = BB.begin(), BE = BB.end(); BI != BE;) {
Chris Lattnerb5557a72009-09-01 17:09:55 +00001339 // Avoid invalidating the iterator.
Duncan P. N. Exon Smithbe4d8cb2015-10-13 19:26:58 +00001340 Instruction *I = &*BI++;
Nadav Rotem465834c2012-07-24 10:51:42 +00001341
Chris Lattner58f9f582010-11-21 00:28:59 +00001342 bool RepeatInstruction = false;
Nadav Rotem465834c2012-07-24 10:51:42 +00001343
Owen Anderson6a7355c2008-04-21 07:45:10 +00001344 if (StoreInst *SI = dyn_cast<StoreInst>(I))
Chris Lattnerb5557a72009-09-01 17:09:55 +00001345 MadeChange |= processStore(SI, BI);
Chris Lattner9a1d63b2011-01-08 21:19:19 +00001346 else if (MemSetInst *M = dyn_cast<MemSetInst>(I))
1347 RepeatInstruction = processMemSet(M, BI);
1348 else if (MemCpyInst *M = dyn_cast<MemCpyInst>(I))
Tim Northover39617352016-05-10 21:49:40 +00001349 RepeatInstruction = processMemCpy(M);
Chris Lattner9a1d63b2011-01-08 21:19:19 +00001350 else if (MemMoveInst *M = dyn_cast<MemMoveInst>(I))
Chris Lattner58f9f582010-11-21 00:28:59 +00001351 RepeatInstruction = processMemMove(M);
Benjamin Kramer3a09ef62015-04-10 14:50:08 +00001352 else if (auto CS = CallSite(I)) {
Chris Lattner58f9f582010-11-21 00:28:59 +00001353 for (unsigned i = 0, e = CS.arg_size(); i != e; ++i)
Nick Lewycky612d70b2011-11-20 19:09:04 +00001354 if (CS.isByValArgument(i))
Chris Lattner58f9f582010-11-21 00:28:59 +00001355 MadeChange |= processByValArgument(CS, i);
1356 }
1357
1358 // Reprocess the instruction if desired.
1359 if (RepeatInstruction) {
Benjamin Kramer135f7352016-06-26 12:28:59 +00001360 if (BI != BB.begin())
1361 --BI;
Chris Lattner58f9f582010-11-21 00:28:59 +00001362 MadeChange = true;
Chris Lattner1145e332009-09-01 17:56:32 +00001363 }
Owen Andersonef9a6fd2008-04-09 08:23:16 +00001364 }
1365 }
Nadav Rotem465834c2012-07-24 10:51:42 +00001366
Chris Lattnerb5557a72009-09-01 17:09:55 +00001367 return MadeChange;
Owen Andersonef9a6fd2008-04-09 08:23:16 +00001368}
Chris Lattnerb5557a72009-09-01 17:09:55 +00001369
Sean Silva6347df02016-06-14 02:44:55 +00001370PreservedAnalyses MemCpyOptPass::run(Function &F, FunctionAnalysisManager &AM) {
Paul Robinsonaf4e64d2014-02-06 00:07:05 +00001371
Sean Silva6347df02016-06-14 02:44:55 +00001372 auto &MD = AM.getResult<MemoryDependenceAnalysis>(F);
1373 auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
1374
1375 auto LookupAliasAnalysis = [&]() -> AliasAnalysis & {
1376 return AM.getResult<AAManager>(F);
1377 };
1378 auto LookupAssumptionCache = [&]() -> AssumptionCache & {
1379 return AM.getResult<AssumptionAnalysis>(F);
1380 };
1381 auto LookupDomTree = [&]() -> DominatorTree & {
1382 return AM.getResult<DominatorTreeAnalysis>(F);
1383 };
1384
1385 bool MadeChange = runImpl(F, &MD, &TLI, LookupAliasAnalysis,
1386 LookupAssumptionCache, LookupDomTree);
1387 if (!MadeChange)
1388 return PreservedAnalyses::all();
1389 PreservedAnalyses PA;
1390 PA.preserve<GlobalsAA>();
1391 PA.preserve<MemoryDependenceAnalysis>();
1392 return PA;
1393}
1394
1395bool MemCpyOptPass::runImpl(
1396 Function &F, MemoryDependenceResults *MD_, TargetLibraryInfo *TLI_,
1397 std::function<AliasAnalysis &()> LookupAliasAnalysis_,
1398 std::function<AssumptionCache &()> LookupAssumptionCache_,
1399 std::function<DominatorTree &()> LookupDomTree_) {
Chris Lattnerb5557a72009-09-01 17:09:55 +00001400 bool MadeChange = false;
Sean Silva6347df02016-06-14 02:44:55 +00001401 MD = MD_;
1402 TLI = TLI_;
Benjamin Kramer1afc1de2016-06-17 20:41:14 +00001403 LookupAliasAnalysis = std::move(LookupAliasAnalysis_);
1404 LookupAssumptionCache = std::move(LookupAssumptionCache_);
1405 LookupDomTree = std::move(LookupDomTree_);
Nadav Rotem465834c2012-07-24 10:51:42 +00001406
Chris Lattner23f61a02011-05-01 18:27:11 +00001407 // If we don't have at least memset and memcpy, there is little point of doing
1408 // anything here. These are required by a freestanding implementation, so if
1409 // even they are disabled, there is no point in trying hard.
1410 if (!TLI->has(LibFunc::memset) || !TLI->has(LibFunc::memcpy))
1411 return false;
Nadav Rotem465834c2012-07-24 10:51:42 +00001412
Chris Lattnerb5557a72009-09-01 17:09:55 +00001413 while (1) {
1414 if (!iterateOnFunction(F))
1415 break;
1416 MadeChange = true;
1417 }
Nadav Rotem465834c2012-07-24 10:51:42 +00001418
Craig Topperf40110f2014-04-25 05:29:35 +00001419 MD = nullptr;
Chris Lattnerb5557a72009-09-01 17:09:55 +00001420 return MadeChange;
1421}
Sean Silva6347df02016-06-14 02:44:55 +00001422
1423/// This is the main transformation entry point for a function.
1424bool MemCpyOptLegacyPass::runOnFunction(Function &F) {
1425 if (skipFunction(F))
1426 return false;
1427
1428 auto *MD = &getAnalysis<MemoryDependenceWrapperPass>().getMemDep();
1429 auto *TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1430
1431 auto LookupAliasAnalysis = [this]() -> AliasAnalysis & {
1432 return getAnalysis<AAResultsWrapperPass>().getAAResults();
1433 };
1434 auto LookupAssumptionCache = [this, &F]() -> AssumptionCache & {
1435 return getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1436 };
1437 auto LookupDomTree = [this]() -> DominatorTree & {
1438 return getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1439 };
1440
1441 return Impl.runImpl(F, MD, TLI, LookupAliasAnalysis, LookupAssumptionCache,
1442 LookupDomTree);
1443}