Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 1 | //===- 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 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 15 | #include "llvm/Transforms/Scalar.h" |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 16 | #include "llvm/ADT/SmallVector.h" |
| 17 | #include "llvm/ADT/Statistic.h" |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 18 | #include "llvm/Analysis/AliasAnalysis.h" |
| 19 | #include "llvm/Analysis/MemoryDependenceAnalysis.h" |
Chris Lattner | 9cb1035 | 2010-12-26 20:15:01 +0000 | [diff] [blame] | 20 | #include "llvm/Analysis/ValueTracking.h" |
Chandler Carruth | 9fb823b | 2013-01-02 11:36:10 +0000 | [diff] [blame] | 21 | #include "llvm/IR/DataLayout.h" |
Chandler Carruth | 5ad5f15 | 2014-01-13 09:26:24 +0000 | [diff] [blame] | 22 | #include "llvm/IR/Dominators.h" |
Chandler Carruth | 03eb0de | 2014-03-04 10:40:04 +0000 | [diff] [blame] | 23 | #include "llvm/IR/GetElementPtrTypeIterator.h" |
Chandler Carruth | 9fb823b | 2013-01-02 11:36:10 +0000 | [diff] [blame] | 24 | #include "llvm/IR/GlobalVariable.h" |
| 25 | #include "llvm/IR/IRBuilder.h" |
| 26 | #include "llvm/IR/Instructions.h" |
| 27 | #include "llvm/IR/IntrinsicInst.h" |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 28 | #include "llvm/Support/Debug.h" |
Chris Lattner | b25de3f | 2009-08-23 04:37:46 +0000 | [diff] [blame] | 29 | #include "llvm/Support/raw_ostream.h" |
Chris Lattner | 23f61a0 | 2011-05-01 18:27:11 +0000 | [diff] [blame] | 30 | #include "llvm/Target/TargetLibraryInfo.h" |
Chandler Carruth | aafe091 | 2012-06-29 12:38:19 +0000 | [diff] [blame] | 31 | #include "llvm/Transforms/Utils/Local.h" |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 32 | #include <list> |
| 33 | using namespace llvm; |
| 34 | |
Chandler Carruth | 964daaa | 2014-04-22 02:55:47 +0000 | [diff] [blame] | 35 | #define DEBUG_TYPE "memcpyopt" |
| 36 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 37 | STATISTIC(NumMemCpyInstr, "Number of memcpy instructions deleted"); |
| 38 | STATISTIC(NumMemSetInfer, "Number of memsets inferred"); |
Duncan Sands | 0edc710 | 2009-09-03 13:37:16 +0000 | [diff] [blame] | 39 | STATISTIC(NumMoveToCpy, "Number of memmoves converted to memcpy"); |
Benjamin Kramer | ea9152e | 2010-12-24 21:17:12 +0000 | [diff] [blame] | 40 | STATISTIC(NumCpyToSet, "Number of memcpys converted to memset"); |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 41 | |
Benjamin Kramer | 15a257d | 2012-09-13 16:29:49 +0000 | [diff] [blame] | 42 | static int64_t GetOffsetFromIndex(const GEPOperator *GEP, unsigned Idx, |
Micah Villmow | cdfe20b | 2012-10-08 16:38:25 +0000 | [diff] [blame] | 43 | bool &VariableIdxFound, const DataLayout &TD){ |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 44 | // Skip over the first indices. |
| 45 | gep_type_iterator GTI = gep_type_begin(GEP); |
| 46 | for (unsigned i = 1; i != Idx; ++i, ++GTI) |
| 47 | /*skip along*/; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 48 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 49 | // Compute the offset implied by the rest of the indices. |
| 50 | int64_t Offset = 0; |
| 51 | for (unsigned i = Idx, e = GEP->getNumOperands(); i != e; ++i, ++GTI) { |
| 52 | ConstantInt *OpC = dyn_cast<ConstantInt>(GEP->getOperand(i)); |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 53 | if (!OpC) |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 54 | return VariableIdxFound = true; |
| 55 | if (OpC->isZero()) continue; // No offset. |
| 56 | |
| 57 | // Handle struct indices, which add their field offset to the pointer. |
Chris Lattner | 229907c | 2011-07-18 04:54:35 +0000 | [diff] [blame] | 58 | if (StructType *STy = dyn_cast<StructType>(*GTI)) { |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 59 | Offset += TD.getStructLayout(STy)->getElementOffset(OpC->getZExtValue()); |
| 60 | continue; |
| 61 | } |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 62 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 63 | // Otherwise, we have a sequential type like an array or vector. Multiply |
| 64 | // the index by the ElementSize. |
Duncan Sands | af9eaa8 | 2009-05-09 07:06:46 +0000 | [diff] [blame] | 65 | uint64_t Size = TD.getTypeAllocSize(GTI.getIndexedType()); |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 66 | Offset += Size*OpC->getSExtValue(); |
| 67 | } |
| 68 | |
| 69 | return Offset; |
| 70 | } |
| 71 | |
| 72 | /// IsPointerOffset - Return true if Ptr1 is provably equal to Ptr2 plus a |
| 73 | /// constant offset, and return that constant offset. For example, Ptr1 might |
| 74 | /// be &A[42], and Ptr2 might be &A[40]. In this case offset would be -8. |
| 75 | static bool IsPointerOffset(Value *Ptr1, Value *Ptr2, int64_t &Offset, |
Micah Villmow | cdfe20b | 2012-10-08 16:38:25 +0000 | [diff] [blame] | 76 | const DataLayout &TD) { |
Chris Lattner | fa7c29d | 2011-01-12 01:43:46 +0000 | [diff] [blame] | 77 | Ptr1 = Ptr1->stripPointerCasts(); |
| 78 | Ptr2 = Ptr2->stripPointerCasts(); |
Benjamin Kramer | 3ef5e46 | 2014-03-10 21:05:13 +0000 | [diff] [blame] | 79 | |
| 80 | // Handle the trivial case first. |
| 81 | if (Ptr1 == Ptr2) { |
| 82 | Offset = 0; |
| 83 | return true; |
| 84 | } |
| 85 | |
Benjamin Kramer | 15a257d | 2012-09-13 16:29:49 +0000 | [diff] [blame] | 86 | GEPOperator *GEP1 = dyn_cast<GEPOperator>(Ptr1); |
| 87 | GEPOperator *GEP2 = dyn_cast<GEPOperator>(Ptr2); |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 88 | |
Chris Lattner | 5120ebf | 2011-01-08 21:07:56 +0000 | [diff] [blame] | 89 | bool VariableIdxFound = false; |
| 90 | |
| 91 | // If one pointer is a GEP and the other isn't, then see if the GEP is a |
| 92 | // constant offset from the base, as in "P" and "gep P, 1". |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 93 | if (GEP1 && !GEP2 && GEP1->getOperand(0)->stripPointerCasts() == Ptr2) { |
Chris Lattner | 5120ebf | 2011-01-08 21:07:56 +0000 | [diff] [blame] | 94 | Offset = -GetOffsetFromIndex(GEP1, 1, VariableIdxFound, TD); |
| 95 | return !VariableIdxFound; |
| 96 | } |
| 97 | |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 98 | if (GEP2 && !GEP1 && GEP2->getOperand(0)->stripPointerCasts() == Ptr1) { |
Chris Lattner | 5120ebf | 2011-01-08 21:07:56 +0000 | [diff] [blame] | 99 | Offset = GetOffsetFromIndex(GEP2, 1, VariableIdxFound, TD); |
| 100 | return !VariableIdxFound; |
| 101 | } |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 102 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 103 | // Right now we handle the case when Ptr1/Ptr2 are both GEPs with an identical |
| 104 | // base. After that base, they may have some number of common (and |
| 105 | // potentially variable) indices. After that they handle some constant |
| 106 | // offset, which determines their offset from each other. At this point, we |
| 107 | // handle no other case. |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 108 | if (!GEP1 || !GEP2 || GEP1->getOperand(0) != GEP2->getOperand(0)) |
| 109 | return false; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 110 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 111 | // Skip any common indices and track the GEP types. |
| 112 | unsigned Idx = 1; |
| 113 | for (; Idx != GEP1->getNumOperands() && Idx != GEP2->getNumOperands(); ++Idx) |
| 114 | if (GEP1->getOperand(Idx) != GEP2->getOperand(Idx)) |
| 115 | break; |
| 116 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 117 | int64_t Offset1 = GetOffsetFromIndex(GEP1, Idx, VariableIdxFound, TD); |
| 118 | int64_t Offset2 = GetOffsetFromIndex(GEP2, Idx, VariableIdxFound, TD); |
| 119 | if (VariableIdxFound) return false; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 120 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 121 | Offset = Offset2-Offset1; |
| 122 | return true; |
| 123 | } |
| 124 | |
| 125 | |
| 126 | /// MemsetRange - Represents a range of memset'd bytes with the ByteVal value. |
| 127 | /// This allows us to analyze stores like: |
| 128 | /// store 0 -> P+1 |
| 129 | /// store 0 -> P+0 |
| 130 | /// store 0 -> P+3 |
| 131 | /// store 0 -> P+2 |
| 132 | /// which sometimes happens with stores to arrays of structs etc. When we see |
| 133 | /// the first store, we make a range [1, 2). The second store extends the range |
| 134 | /// to [0, 2). The third makes a new range [2, 3). The fourth store joins the |
| 135 | /// two ranges into [0, 3) which is memset'able. |
| 136 | namespace { |
| 137 | struct MemsetRange { |
| 138 | // Start/End - A semi range that describes the span that this range covers. |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 139 | // The range is closed at the start and open at the end: [Start, End). |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 140 | int64_t Start, End; |
| 141 | |
| 142 | /// StartPtr - The getelementptr instruction that points to the start of the |
| 143 | /// range. |
| 144 | Value *StartPtr; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 145 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 146 | /// Alignment - The known alignment of the first store. |
| 147 | unsigned Alignment; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 148 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 149 | /// TheStores - The actual stores that make up this range. |
Chris Lattner | 4dc1fd9 | 2011-01-08 20:54:51 +0000 | [diff] [blame] | 150 | SmallVector<Instruction*, 16> TheStores; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 151 | |
Micah Villmow | cdfe20b | 2012-10-08 16:38:25 +0000 | [diff] [blame] | 152 | bool isProfitableToUseMemset(const DataLayout &TD) const; |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 153 | |
| 154 | }; |
| 155 | } // end anon namespace |
| 156 | |
Micah Villmow | cdfe20b | 2012-10-08 16:38:25 +0000 | [diff] [blame] | 157 | bool MemsetRange::isProfitableToUseMemset(const DataLayout &TD) const { |
Chad Rosier | 3277557 | 2011-12-05 22:53:09 +0000 | [diff] [blame] | 158 | // If we found more than 4 stores to merge or 16 bytes, use memset. |
Chad Rosier | 19446a0 | 2011-12-05 22:37:00 +0000 | [diff] [blame] | 159 | if (TheStores.size() >= 4 || End-Start >= 16) return true; |
Chris Lattner | 4dc1fd9 | 2011-01-08 20:54:51 +0000 | [diff] [blame] | 160 | |
| 161 | // If there is nothing to merge, don't do anything. |
| 162 | if (TheStores.size() < 2) return false; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 163 | |
Chris Lattner | 4dc1fd9 | 2011-01-08 20:54:51 +0000 | [diff] [blame] | 164 | // If any of the stores are a memset, then it is always good to extend the |
| 165 | // memset. |
| 166 | for (unsigned i = 0, e = TheStores.size(); i != e; ++i) |
| 167 | if (!isa<StoreInst>(TheStores[i])) |
| 168 | return true; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 169 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 170 | // Assume that the code generator is capable of merging pairs of stores |
| 171 | // together if it wants to. |
Chris Lattner | 4dc1fd9 | 2011-01-08 20:54:51 +0000 | [diff] [blame] | 172 | if (TheStores.size() == 2) return false; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 173 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 174 | // If we have fewer than 8 stores, it can still be worthwhile to do this. |
| 175 | // For example, merging 4 i8 stores into an i32 store is useful almost always. |
| 176 | // However, merging 2 32-bit stores isn't useful on a 32-bit architecture (the |
| 177 | // memset will be split into 2 32-bit stores anyway) and doing so can |
| 178 | // pessimize the llvm optimizer. |
| 179 | // |
| 180 | // Since we don't have perfect knowledge here, make some assumptions: assume |
Matt Arsenault | 899f7d2 | 2013-09-16 22:43:16 +0000 | [diff] [blame] | 181 | // the maximum GPR width is the same size as the largest legal integer |
| 182 | // size. If so, check to see whether we will end up actually reducing the |
| 183 | // number of stores used. |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 184 | unsigned Bytes = unsigned(End-Start); |
Matt Arsenault | 899f7d2 | 2013-09-16 22:43:16 +0000 | [diff] [blame] | 185 | unsigned MaxIntSize = TD.getLargestLegalIntTypeSize(); |
| 186 | if (MaxIntSize == 0) |
| 187 | MaxIntSize = 1; |
| 188 | unsigned NumPointerStores = Bytes / MaxIntSize; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 189 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 190 | // Assume the remaining bytes if any are done a byte at a time. |
Matt Arsenault | 899f7d2 | 2013-09-16 22:43:16 +0000 | [diff] [blame] | 191 | unsigned NumByteStores = Bytes - NumPointerStores * MaxIntSize; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 192 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 193 | // If we will reduce the # stores (according to this heuristic), do the |
| 194 | // transformation. This encourages merging 4 x i8 -> i32 and 2 x i16 -> i32 |
| 195 | // etc. |
| 196 | return TheStores.size() > NumPointerStores+NumByteStores; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 197 | } |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 198 | |
| 199 | |
| 200 | namespace { |
| 201 | class MemsetRanges { |
| 202 | /// Ranges - A sorted list of the memset ranges. We use std::list here |
| 203 | /// because each element is relatively large and expensive to copy. |
| 204 | std::list<MemsetRange> Ranges; |
| 205 | typedef std::list<MemsetRange>::iterator range_iterator; |
Rafael Espindola | 37dc9e1 | 2014-02-21 00:06:31 +0000 | [diff] [blame] | 206 | const DataLayout &DL; |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 207 | public: |
Rafael Espindola | 37dc9e1 | 2014-02-21 00:06:31 +0000 | [diff] [blame] | 208 | MemsetRanges(const DataLayout &DL) : DL(DL) {} |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 209 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 210 | typedef std::list<MemsetRange>::const_iterator const_iterator; |
| 211 | const_iterator begin() const { return Ranges.begin(); } |
| 212 | const_iterator end() const { return Ranges.end(); } |
| 213 | bool empty() const { return Ranges.empty(); } |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 214 | |
Chris Lattner | c638147 | 2011-01-08 20:24:01 +0000 | [diff] [blame] | 215 | void addInst(int64_t OffsetFromFirst, Instruction *Inst) { |
Chris Lattner | 4dc1fd9 | 2011-01-08 20:54:51 +0000 | [diff] [blame] | 216 | if (StoreInst *SI = dyn_cast<StoreInst>(Inst)) |
| 217 | addStore(OffsetFromFirst, SI); |
| 218 | else |
| 219 | addMemSet(OffsetFromFirst, cast<MemSetInst>(Inst)); |
Chris Lattner | c638147 | 2011-01-08 20:24:01 +0000 | [diff] [blame] | 220 | } |
Chris Lattner | 4dc1fd9 | 2011-01-08 20:54:51 +0000 | [diff] [blame] | 221 | |
| 222 | void addStore(int64_t OffsetFromFirst, StoreInst *SI) { |
Rafael Espindola | 37dc9e1 | 2014-02-21 00:06:31 +0000 | [diff] [blame] | 223 | int64_t StoreSize = DL.getTypeStoreSize(SI->getOperand(0)->getType()); |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 224 | |
Chris Lattner | 4dc1fd9 | 2011-01-08 20:54:51 +0000 | [diff] [blame] | 225 | addRange(OffsetFromFirst, StoreSize, |
| 226 | SI->getPointerOperand(), SI->getAlignment(), SI); |
| 227 | } |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 228 | |
Chris Lattner | 4dc1fd9 | 2011-01-08 20:54:51 +0000 | [diff] [blame] | 229 | void addMemSet(int64_t OffsetFromFirst, MemSetInst *MSI) { |
| 230 | int64_t Size = cast<ConstantInt>(MSI->getLength())->getZExtValue(); |
| 231 | addRange(OffsetFromFirst, Size, MSI->getDest(), MSI->getAlignment(), MSI); |
| 232 | } |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 233 | |
Chris Lattner | 4dc1fd9 | 2011-01-08 20:54:51 +0000 | [diff] [blame] | 234 | void addRange(int64_t Start, int64_t Size, Value *Ptr, |
| 235 | unsigned Alignment, Instruction *Inst); |
| 236 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 237 | }; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 238 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 239 | } // end anon namespace |
| 240 | |
| 241 | |
Chris Lattner | 4dc1fd9 | 2011-01-08 20:54:51 +0000 | [diff] [blame] | 242 | /// addRange - Add a new store to the MemsetRanges data structure. This adds a |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 243 | /// new range for the specified store at the specified offset, merging into |
| 244 | /// existing ranges as appropriate. |
Chris Lattner | 4dc1fd9 | 2011-01-08 20:54:51 +0000 | [diff] [blame] | 245 | /// |
| 246 | /// Do a linear search of the ranges to see if this can be joined and/or to |
| 247 | /// find the insertion point in the list. We keep the ranges sorted for |
| 248 | /// simplicity here. This is a linear search of a linked list, which is ugly, |
| 249 | /// however the number of ranges is limited, so this won't get crazy slow. |
| 250 | void MemsetRanges::addRange(int64_t Start, int64_t Size, Value *Ptr, |
| 251 | unsigned Alignment, Instruction *Inst) { |
| 252 | int64_t End = Start+Size; |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 253 | range_iterator I = Ranges.begin(), E = Ranges.end(); |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 254 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 255 | while (I != E && Start > I->End) |
| 256 | ++I; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 257 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 258 | // We now know that I == E, in which case we didn't find anything to merge |
| 259 | // with, or that Start <= I->End. If End < I->Start or I == E, then we need |
| 260 | // to insert a new range. Handle this now. |
| 261 | if (I == E || End < I->Start) { |
| 262 | MemsetRange &R = *Ranges.insert(I, MemsetRange()); |
| 263 | R.Start = Start; |
| 264 | R.End = End; |
Chris Lattner | 4dc1fd9 | 2011-01-08 20:54:51 +0000 | [diff] [blame] | 265 | R.StartPtr = Ptr; |
| 266 | R.Alignment = Alignment; |
| 267 | R.TheStores.push_back(Inst); |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 268 | return; |
| 269 | } |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 270 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 271 | // This store overlaps with I, add it. |
Chris Lattner | 4dc1fd9 | 2011-01-08 20:54:51 +0000 | [diff] [blame] | 272 | I->TheStores.push_back(Inst); |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 273 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 274 | // At this point, we may have an interval that completely contains our store. |
| 275 | // If so, just add it to the interval and return. |
| 276 | if (I->Start <= Start && I->End >= End) |
| 277 | return; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 278 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 279 | // Now we know that Start <= I->End and End >= I->Start so the range overlaps |
| 280 | // but is not entirely contained within the range. |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 281 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 282 | // See if the range extends the start of the range. In this case, it couldn't |
| 283 | // possibly cause it to join the prior range, because otherwise we would have |
| 284 | // stopped on *it*. |
| 285 | if (Start < I->Start) { |
| 286 | I->Start = Start; |
Chris Lattner | 4dc1fd9 | 2011-01-08 20:54:51 +0000 | [diff] [blame] | 287 | I->StartPtr = Ptr; |
| 288 | I->Alignment = Alignment; |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 289 | } |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 290 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 291 | // Now we know that Start <= I->End and Start >= I->Start (so the startpoint |
| 292 | // is in or right at the end of I), and that End >= I->Start. Extend I out to |
| 293 | // End. |
| 294 | if (End > I->End) { |
| 295 | I->End = End; |
Nick Lewycky | bfd4ad6 | 2009-03-19 05:51:39 +0000 | [diff] [blame] | 296 | range_iterator NextI = I; |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 297 | while (++NextI != E && End >= NextI->Start) { |
| 298 | // Merge the range in. |
| 299 | I->TheStores.append(NextI->TheStores.begin(), NextI->TheStores.end()); |
| 300 | if (NextI->End > I->End) |
| 301 | I->End = NextI->End; |
| 302 | Ranges.erase(NextI); |
| 303 | NextI = I; |
| 304 | } |
| 305 | } |
| 306 | } |
| 307 | |
| 308 | //===----------------------------------------------------------------------===// |
| 309 | // MemCpyOpt Pass |
| 310 | //===----------------------------------------------------------------------===// |
| 311 | |
| 312 | namespace { |
Chris Lattner | 2dd09db | 2009-09-02 06:11:42 +0000 | [diff] [blame] | 313 | class MemCpyOpt : public FunctionPass { |
Chris Lattner | 58f9f58 | 2010-11-21 00:28:59 +0000 | [diff] [blame] | 314 | MemoryDependenceAnalysis *MD; |
Chris Lattner | 23f61a0 | 2011-05-01 18:27:11 +0000 | [diff] [blame] | 315 | TargetLibraryInfo *TLI; |
Rafael Espindola | 37dc9e1 | 2014-02-21 00:06:31 +0000 | [diff] [blame] | 316 | const DataLayout *DL; |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 317 | public: |
| 318 | static char ID; // Pass identification, replacement for typeid |
Owen Anderson | 6c18d1a | 2010-10-19 17:21:58 +0000 | [diff] [blame] | 319 | MemCpyOpt() : FunctionPass(ID) { |
| 320 | initializeMemCpyOptPass(*PassRegistry::getPassRegistry()); |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 321 | MD = nullptr; |
| 322 | TLI = nullptr; |
| 323 | DL = nullptr; |
Owen Anderson | 6c18d1a | 2010-10-19 17:21:58 +0000 | [diff] [blame] | 324 | } |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 325 | |
Craig Topper | 3e4c697 | 2014-03-05 09:10:37 +0000 | [diff] [blame] | 326 | bool runOnFunction(Function &F) override; |
Chris Lattner | c638147 | 2011-01-08 20:24:01 +0000 | [diff] [blame] | 327 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 328 | private: |
| 329 | // This transformation requires dominator postdominator info |
Craig Topper | 3e4c697 | 2014-03-05 09:10:37 +0000 | [diff] [blame] | 330 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 331 | AU.setPreservesCFG(); |
Chandler Carruth | 7352302 | 2014-01-13 13:07:17 +0000 | [diff] [blame] | 332 | AU.addRequired<DominatorTreeWrapperPass>(); |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 333 | AU.addRequired<MemoryDependenceAnalysis>(); |
| 334 | AU.addRequired<AliasAnalysis>(); |
Chris Lattner | 23f61a0 | 2011-05-01 18:27:11 +0000 | [diff] [blame] | 335 | AU.addRequired<TargetLibraryInfo>(); |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 336 | AU.addPreserved<AliasAnalysis>(); |
| 337 | AU.addPreserved<MemoryDependenceAnalysis>(); |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 338 | } |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 339 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 340 | // Helper fuctions |
Chris Lattner | b5557a7 | 2009-09-01 17:09:55 +0000 | [diff] [blame] | 341 | bool processStore(StoreInst *SI, BasicBlock::iterator &BBI); |
Chris Lattner | 9a1d63b | 2011-01-08 21:19:19 +0000 | [diff] [blame] | 342 | bool processMemSet(MemSetInst *SI, BasicBlock::iterator &BBI); |
Chris Lattner | b5557a7 | 2009-09-01 17:09:55 +0000 | [diff] [blame] | 343 | bool processMemCpy(MemCpyInst *M); |
Chris Lattner | 1145e33 | 2009-09-01 17:56:32 +0000 | [diff] [blame] | 344 | bool processMemMove(MemMoveInst *M); |
Owen Anderson | 18e4fed | 2010-10-15 22:52:12 +0000 | [diff] [blame] | 345 | bool performCallSlotOptzn(Instruction *cpy, Value *cpyDst, Value *cpySrc, |
Duncan Sands | c6ada69 | 2012-10-04 10:54:40 +0000 | [diff] [blame] | 346 | uint64_t cpyLen, unsigned cpyAlign, CallInst *C); |
Chris Lattner | 7e9b2ea | 2010-11-18 07:02:37 +0000 | [diff] [blame] | 347 | bool processMemCpyMemCpyDependence(MemCpyInst *M, MemCpyInst *MDep, |
| 348 | uint64_t MSize); |
Chris Lattner | 58f9f58 | 2010-11-21 00:28:59 +0000 | [diff] [blame] | 349 | bool processByValArgument(CallSite CS, unsigned ArgNo); |
Chris Lattner | c638147 | 2011-01-08 20:24:01 +0000 | [diff] [blame] | 350 | Instruction *tryMergingIntoMemset(Instruction *I, Value *StartPtr, |
| 351 | Value *ByteVal); |
| 352 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 353 | bool iterateOnFunction(Function &F); |
| 354 | }; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 355 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 356 | char MemCpyOpt::ID = 0; |
| 357 | } |
| 358 | |
| 359 | // createMemCpyOptPass - The public interface to this file... |
| 360 | FunctionPass *llvm::createMemCpyOptPass() { return new MemCpyOpt(); } |
| 361 | |
Owen Anderson | 8ac477f | 2010-10-12 19:48:12 +0000 | [diff] [blame] | 362 | INITIALIZE_PASS_BEGIN(MemCpyOpt, "memcpyopt", "MemCpy Optimization", |
| 363 | false, false) |
Chandler Carruth | 7352302 | 2014-01-13 13:07:17 +0000 | [diff] [blame] | 364 | INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) |
Owen Anderson | 8ac477f | 2010-10-12 19:48:12 +0000 | [diff] [blame] | 365 | INITIALIZE_PASS_DEPENDENCY(MemoryDependenceAnalysis) |
Chris Lattner | 23f61a0 | 2011-05-01 18:27:11 +0000 | [diff] [blame] | 366 | INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) |
Owen Anderson | 8ac477f | 2010-10-12 19:48:12 +0000 | [diff] [blame] | 367 | INITIALIZE_AG_DEPENDENCY(AliasAnalysis) |
| 368 | INITIALIZE_PASS_END(MemCpyOpt, "memcpyopt", "MemCpy Optimization", |
| 369 | false, false) |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 370 | |
Chris Lattner | c638147 | 2011-01-08 20:24:01 +0000 | [diff] [blame] | 371 | /// tryMergingIntoMemset - When scanning forward over instructions, we look for |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 372 | /// some other patterns to fold away. In particular, this looks for stores to |
Duncan Sands | 75b5d27 | 2011-02-15 09:23:02 +0000 | [diff] [blame] | 373 | /// neighboring locations of memory. If it sees enough consecutive ones, it |
Chris Lattner | c638147 | 2011-01-08 20:24:01 +0000 | [diff] [blame] | 374 | /// attempts to merge them together into a memcpy/memset. |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 375 | Instruction *MemCpyOpt::tryMergingIntoMemset(Instruction *StartInst, |
Chris Lattner | c638147 | 2011-01-08 20:24:01 +0000 | [diff] [blame] | 376 | Value *StartPtr, Value *ByteVal) { |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 377 | if (!DL) return nullptr; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 378 | |
Chris Lattner | c638147 | 2011-01-08 20:24:01 +0000 | [diff] [blame] | 379 | // Okay, so we now have a single store that can be splatable. Scan to find |
| 380 | // all subsequent stores of the same value to offset from the same pointer. |
| 381 | // Join these together into ranges, so we can decide whether contiguous blocks |
| 382 | // are stored. |
Rafael Espindola | 37dc9e1 | 2014-02-21 00:06:31 +0000 | [diff] [blame] | 383 | MemsetRanges Ranges(*DL); |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 384 | |
Chris Lattner | c638147 | 2011-01-08 20:24:01 +0000 | [diff] [blame] | 385 | BasicBlock::iterator BI = StartInst; |
| 386 | for (++BI; !isa<TerminatorInst>(BI); ++BI) { |
Chris Lattner | 4dc1fd9 | 2011-01-08 20:54:51 +0000 | [diff] [blame] | 387 | if (!isa<StoreInst>(BI) && !isa<MemSetInst>(BI)) { |
| 388 | // If the instruction is readnone, ignore it, otherwise bail out. We |
| 389 | // don't even allow readonly here because we don't want something like: |
Chris Lattner | c638147 | 2011-01-08 20:24:01 +0000 | [diff] [blame] | 390 | // A[1] = 2; strlen(A); A[2] = 2; -> memcpy(A, ...); strlen(A). |
Chris Lattner | 4dc1fd9 | 2011-01-08 20:54:51 +0000 | [diff] [blame] | 391 | if (BI->mayWriteToMemory() || BI->mayReadFromMemory()) |
| 392 | break; |
| 393 | continue; |
| 394 | } |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 395 | |
Chris Lattner | 4dc1fd9 | 2011-01-08 20:54:51 +0000 | [diff] [blame] | 396 | if (StoreInst *NextStore = dyn_cast<StoreInst>(BI)) { |
| 397 | // If this is a store, see if we can merge it in. |
Eli Friedman | 9a46815 | 2011-08-17 22:22:24 +0000 | [diff] [blame] | 398 | if (!NextStore->isSimple()) break; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 399 | |
Chris Lattner | 4dc1fd9 | 2011-01-08 20:54:51 +0000 | [diff] [blame] | 400 | // Check to see if this stored value is of the same byte-splattable value. |
| 401 | if (ByteVal != isBytewiseValue(NextStore->getOperand(0))) |
| 402 | break; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 403 | |
Chris Lattner | 4dc1fd9 | 2011-01-08 20:54:51 +0000 | [diff] [blame] | 404 | // Check to see if this store is to a constant offset from the start ptr. |
| 405 | int64_t Offset; |
Chris Lattner | caf5c0d | 2011-01-09 19:26:10 +0000 | [diff] [blame] | 406 | if (!IsPointerOffset(StartPtr, NextStore->getPointerOperand(), |
Rafael Espindola | 37dc9e1 | 2014-02-21 00:06:31 +0000 | [diff] [blame] | 407 | Offset, *DL)) |
Chris Lattner | 4dc1fd9 | 2011-01-08 20:54:51 +0000 | [diff] [blame] | 408 | break; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 409 | |
Chris Lattner | 4dc1fd9 | 2011-01-08 20:54:51 +0000 | [diff] [blame] | 410 | Ranges.addStore(Offset, NextStore); |
| 411 | } else { |
| 412 | MemSetInst *MSI = cast<MemSetInst>(BI); |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 413 | |
Chris Lattner | 4dc1fd9 | 2011-01-08 20:54:51 +0000 | [diff] [blame] | 414 | if (MSI->isVolatile() || ByteVal != MSI->getValue() || |
| 415 | !isa<ConstantInt>(MSI->getLength())) |
| 416 | break; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 417 | |
Chris Lattner | 4dc1fd9 | 2011-01-08 20:54:51 +0000 | [diff] [blame] | 418 | // Check to see if this store is to a constant offset from the start ptr. |
| 419 | int64_t Offset; |
Rafael Espindola | 37dc9e1 | 2014-02-21 00:06:31 +0000 | [diff] [blame] | 420 | if (!IsPointerOffset(StartPtr, MSI->getDest(), Offset, *DL)) |
Chris Lattner | 4dc1fd9 | 2011-01-08 20:54:51 +0000 | [diff] [blame] | 421 | break; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 422 | |
Chris Lattner | 4dc1fd9 | 2011-01-08 20:54:51 +0000 | [diff] [blame] | 423 | Ranges.addMemSet(Offset, MSI); |
| 424 | } |
Chris Lattner | c638147 | 2011-01-08 20:24:01 +0000 | [diff] [blame] | 425 | } |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 426 | |
Chris Lattner | c638147 | 2011-01-08 20:24:01 +0000 | [diff] [blame] | 427 | // If we have no ranges, then we just had a single store with nothing that |
| 428 | // could be merged in. This is a very common case of course. |
| 429 | if (Ranges.empty()) |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 430 | return nullptr; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 431 | |
Chris Lattner | c638147 | 2011-01-08 20:24:01 +0000 | [diff] [blame] | 432 | // If we had at least one store that could be merged in, add the starting |
| 433 | // store as well. We try to avoid this unless there is at least something |
| 434 | // interesting as a small compile-time optimization. |
| 435 | Ranges.addInst(0, StartInst); |
| 436 | |
| 437 | // If we create any memsets, we put it right before the first instruction that |
| 438 | // isn't part of the memset block. This ensure that the memset is dominated |
| 439 | // by any addressing instruction needed by the start of the block. |
| 440 | IRBuilder<> Builder(BI); |
| 441 | |
| 442 | // Now that we have full information about ranges, loop over the ranges and |
| 443 | // emit memset's for anything big enough to be worthwhile. |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 444 | Instruction *AMemSet = nullptr; |
Chris Lattner | c638147 | 2011-01-08 20:24:01 +0000 | [diff] [blame] | 445 | for (MemsetRanges::const_iterator I = Ranges.begin(), E = Ranges.end(); |
| 446 | I != E; ++I) { |
| 447 | const MemsetRange &Range = *I; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 448 | |
Chris Lattner | c638147 | 2011-01-08 20:24:01 +0000 | [diff] [blame] | 449 | if (Range.TheStores.size() == 1) continue; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 450 | |
Chris Lattner | c638147 | 2011-01-08 20:24:01 +0000 | [diff] [blame] | 451 | // If it is profitable to lower this range to memset, do so now. |
Rafael Espindola | 37dc9e1 | 2014-02-21 00:06:31 +0000 | [diff] [blame] | 452 | if (!Range.isProfitableToUseMemset(*DL)) |
Chris Lattner | c638147 | 2011-01-08 20:24:01 +0000 | [diff] [blame] | 453 | continue; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 454 | |
Chris Lattner | c638147 | 2011-01-08 20:24:01 +0000 | [diff] [blame] | 455 | // Otherwise, we do want to transform this! Create a new memset. |
| 456 | // Get the starting pointer of the block. |
| 457 | StartPtr = Range.StartPtr; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 458 | |
Chris Lattner | c638147 | 2011-01-08 20:24:01 +0000 | [diff] [blame] | 459 | // Determine alignment |
| 460 | unsigned Alignment = Range.Alignment; |
| 461 | if (Alignment == 0) { |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 462 | Type *EltType = |
Chris Lattner | c638147 | 2011-01-08 20:24:01 +0000 | [diff] [blame] | 463 | cast<PointerType>(StartPtr->getType())->getElementType(); |
Rafael Espindola | 37dc9e1 | 2014-02-21 00:06:31 +0000 | [diff] [blame] | 464 | Alignment = DL->getABITypeAlignment(EltType); |
Chris Lattner | c638147 | 2011-01-08 20:24:01 +0000 | [diff] [blame] | 465 | } |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 466 | |
| 467 | AMemSet = |
Chris Lattner | c638147 | 2011-01-08 20:24:01 +0000 | [diff] [blame] | 468 | Builder.CreateMemSet(StartPtr, ByteVal, Range.End-Range.Start, Alignment); |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 469 | |
Chris Lattner | c638147 | 2011-01-08 20:24:01 +0000 | [diff] [blame] | 470 | DEBUG(dbgs() << "Replace stores:\n"; |
| 471 | for (unsigned i = 0, e = Range.TheStores.size(); i != e; ++i) |
| 472 | dbgs() << *Range.TheStores[i] << '\n'; |
| 473 | dbgs() << "With: " << *AMemSet << '\n'); |
Devang Patel | c7e4fa7 | 2011-05-04 21:58:58 +0000 | [diff] [blame] | 474 | |
| 475 | if (!Range.TheStores.empty()) |
| 476 | AMemSet->setDebugLoc(Range.TheStores[0]->getDebugLoc()); |
| 477 | |
Chris Lattner | c638147 | 2011-01-08 20:24:01 +0000 | [diff] [blame] | 478 | // Zap all the stores. |
Craig Topper | 31ee586 | 2013-07-03 15:07:05 +0000 | [diff] [blame] | 479 | for (SmallVectorImpl<Instruction *>::const_iterator |
Chris Lattner | c638147 | 2011-01-08 20:24:01 +0000 | [diff] [blame] | 480 | SI = Range.TheStores.begin(), |
Chris Lattner | 7d6433a | 2011-01-08 22:19:21 +0000 | [diff] [blame] | 481 | SE = Range.TheStores.end(); SI != SE; ++SI) { |
| 482 | MD->removeInstruction(*SI); |
Chris Lattner | c638147 | 2011-01-08 20:24:01 +0000 | [diff] [blame] | 483 | (*SI)->eraseFromParent(); |
Chris Lattner | 7d6433a | 2011-01-08 22:19:21 +0000 | [diff] [blame] | 484 | } |
Chris Lattner | c638147 | 2011-01-08 20:24:01 +0000 | [diff] [blame] | 485 | ++NumMemSetInfer; |
| 486 | } |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 487 | |
Chris Lattner | c638147 | 2011-01-08 20:24:01 +0000 | [diff] [blame] | 488 | return AMemSet; |
| 489 | } |
| 490 | |
| 491 | |
Chris Lattner | b5557a7 | 2009-09-01 17:09:55 +0000 | [diff] [blame] | 492 | bool MemCpyOpt::processStore(StoreInst *SI, BasicBlock::iterator &BBI) { |
Eli Friedman | 9a46815 | 2011-08-17 22:22:24 +0000 | [diff] [blame] | 493 | if (!SI->isSimple()) return false; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 494 | |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 495 | if (!DL) return false; |
Owen Anderson | 18e4fed | 2010-10-15 22:52:12 +0000 | [diff] [blame] | 496 | |
| 497 | // Detect cases where we're performing call slot forwarding, but |
| 498 | // happen to be using a load-store pair to implement it, rather than |
| 499 | // a memcpy. |
| 500 | if (LoadInst *LI = dyn_cast<LoadInst>(SI->getOperand(0))) { |
Eli Friedman | 9a46815 | 2011-08-17 22:22:24 +0000 | [diff] [blame] | 501 | if (LI->isSimple() && LI->hasOneUse() && |
Eli Friedman | e8bbc10 | 2011-06-15 01:25:56 +0000 | [diff] [blame] | 502 | LI->getParent() == SI->getParent()) { |
Eli Friedman | 5da0ff4 | 2011-06-02 21:24:42 +0000 | [diff] [blame] | 503 | MemDepResult ldep = MD->getDependency(LI); |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 504 | CallInst *C = nullptr; |
Eli Friedman | 5da0ff4 | 2011-06-02 21:24:42 +0000 | [diff] [blame] | 505 | if (ldep.isClobber() && !isa<MemCpyInst>(ldep.getInst())) |
| 506 | C = dyn_cast<CallInst>(ldep.getInst()); |
| 507 | |
| 508 | if (C) { |
| 509 | // Check that nothing touches the dest of the "copy" between |
| 510 | // the call and the store. |
Eli Friedman | e8bbc10 | 2011-06-15 01:25:56 +0000 | [diff] [blame] | 511 | AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); |
| 512 | AliasAnalysis::Location StoreLoc = AA.getLocation(SI); |
| 513 | for (BasicBlock::iterator I = --BasicBlock::iterator(SI), |
| 514 | E = C; I != E; --I) { |
| 515 | if (AA.getModRefInfo(&*I, StoreLoc) != AliasAnalysis::NoModRef) { |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 516 | C = nullptr; |
Eli Friedman | e8bbc10 | 2011-06-15 01:25:56 +0000 | [diff] [blame] | 517 | break; |
| 518 | } |
Eli Friedman | 5da0ff4 | 2011-06-02 21:24:42 +0000 | [diff] [blame] | 519 | } |
| 520 | } |
| 521 | |
Owen Anderson | 18e4fed | 2010-10-15 22:52:12 +0000 | [diff] [blame] | 522 | if (C) { |
Duncan Sands | c6ada69 | 2012-10-04 10:54:40 +0000 | [diff] [blame] | 523 | unsigned storeAlign = SI->getAlignment(); |
| 524 | if (!storeAlign) |
Rafael Espindola | 37dc9e1 | 2014-02-21 00:06:31 +0000 | [diff] [blame] | 525 | storeAlign = DL->getABITypeAlignment(SI->getOperand(0)->getType()); |
Duncan Sands | c6ada69 | 2012-10-04 10:54:40 +0000 | [diff] [blame] | 526 | unsigned loadAlign = LI->getAlignment(); |
| 527 | if (!loadAlign) |
Rafael Espindola | 37dc9e1 | 2014-02-21 00:06:31 +0000 | [diff] [blame] | 528 | loadAlign = DL->getABITypeAlignment(LI->getType()); |
Duncan Sands | c6ada69 | 2012-10-04 10:54:40 +0000 | [diff] [blame] | 529 | |
Owen Anderson | 18e4fed | 2010-10-15 22:52:12 +0000 | [diff] [blame] | 530 | bool changed = performCallSlotOptzn(LI, |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 531 | SI->getPointerOperand()->stripPointerCasts(), |
Owen Anderson | 18e4fed | 2010-10-15 22:52:12 +0000 | [diff] [blame] | 532 | LI->getPointerOperand()->stripPointerCasts(), |
Rafael Espindola | 37dc9e1 | 2014-02-21 00:06:31 +0000 | [diff] [blame] | 533 | DL->getTypeStoreSize(SI->getOperand(0)->getType()), |
Duncan Sands | c6ada69 | 2012-10-04 10:54:40 +0000 | [diff] [blame] | 534 | std::min(storeAlign, loadAlign), C); |
Owen Anderson | 18e4fed | 2010-10-15 22:52:12 +0000 | [diff] [blame] | 535 | if (changed) { |
Chris Lattner | 58f9f58 | 2010-11-21 00:28:59 +0000 | [diff] [blame] | 536 | MD->removeInstruction(SI); |
Owen Anderson | 18e4fed | 2010-10-15 22:52:12 +0000 | [diff] [blame] | 537 | SI->eraseFromParent(); |
Chris Lattner | caf5c0d | 2011-01-09 19:26:10 +0000 | [diff] [blame] | 538 | MD->removeInstruction(LI); |
Owen Anderson | 18e4fed | 2010-10-15 22:52:12 +0000 | [diff] [blame] | 539 | LI->eraseFromParent(); |
| 540 | ++NumMemCpyInstr; |
| 541 | return true; |
| 542 | } |
| 543 | } |
| 544 | } |
| 545 | } |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 546 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 547 | // There are two cases that are interesting for this code to handle: memcpy |
| 548 | // and memset. Right now we only handle memset. |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 549 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 550 | // Ensure that the value being stored is something that can be memset'able a |
| 551 | // byte at a time like "0" or "-1" or any width, as well as things like |
| 552 | // 0xA0A0A0A0 and 0.0. |
Chris Lattner | c638147 | 2011-01-08 20:24:01 +0000 | [diff] [blame] | 553 | if (Value *ByteVal = isBytewiseValue(SI->getOperand(0))) |
| 554 | if (Instruction *I = tryMergingIntoMemset(SI, SI->getPointerOperand(), |
| 555 | ByteVal)) { |
| 556 | BBI = I; // Don't invalidate iterator. |
| 557 | return true; |
Mon P Wang | c576ee9 | 2010-04-04 03:10:48 +0000 | [diff] [blame] | 558 | } |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 559 | |
Chris Lattner | c638147 | 2011-01-08 20:24:01 +0000 | [diff] [blame] | 560 | return false; |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 561 | } |
| 562 | |
Chris Lattner | 9a1d63b | 2011-01-08 21:19:19 +0000 | [diff] [blame] | 563 | bool MemCpyOpt::processMemSet(MemSetInst *MSI, BasicBlock::iterator &BBI) { |
| 564 | // See if there is another memset or store neighboring this memset which |
| 565 | // allows us to widen out the memset to do a single larger store. |
Chris Lattner | ff6ed2a | 2011-01-08 22:11:56 +0000 | [diff] [blame] | 566 | if (isa<ConstantInt>(MSI->getLength()) && !MSI->isVolatile()) |
| 567 | if (Instruction *I = tryMergingIntoMemset(MSI, MSI->getDest(), |
| 568 | MSI->getValue())) { |
| 569 | BBI = I; // Don't invalidate iterator. |
| 570 | return true; |
| 571 | } |
Chris Lattner | 9a1d63b | 2011-01-08 21:19:19 +0000 | [diff] [blame] | 572 | return false; |
| 573 | } |
| 574 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 575 | |
| 576 | /// performCallSlotOptzn - takes a memcpy and a call that it depends on, |
| 577 | /// and checks for the possibility of a call slot optimization by having |
| 578 | /// the call write its result directly into the destination of the memcpy. |
Owen Anderson | 18e4fed | 2010-10-15 22:52:12 +0000 | [diff] [blame] | 579 | bool MemCpyOpt::performCallSlotOptzn(Instruction *cpy, |
| 580 | Value *cpyDest, Value *cpySrc, |
Duncan Sands | c6ada69 | 2012-10-04 10:54:40 +0000 | [diff] [blame] | 581 | uint64_t cpyLen, unsigned cpyAlign, |
| 582 | CallInst *C) { |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 583 | // The general transformation to keep in mind is |
| 584 | // |
| 585 | // call @func(..., src, ...) |
| 586 | // memcpy(dest, src, ...) |
| 587 | // |
| 588 | // -> |
| 589 | // |
| 590 | // memcpy(dest, src, ...) |
| 591 | // call @func(..., dest, ...) |
| 592 | // |
| 593 | // Since moving the memcpy is technically awkward, we additionally check that |
| 594 | // src only holds uninitialized values at the moment of the call, meaning that |
| 595 | // the memcpy can be discarded rather than moved. |
| 596 | |
| 597 | // Deliberately get the source and destination with bitcasts stripped away, |
| 598 | // because we'll need to do type comparisons based on the underlying type. |
Gabor Greif | 62f0aac | 2010-07-28 22:50:26 +0000 | [diff] [blame] | 599 | CallSite CS(C); |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 600 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 601 | // Require that src be an alloca. This simplifies the reasoning considerably. |
Chris Lattner | b5557a7 | 2009-09-01 17:09:55 +0000 | [diff] [blame] | 602 | AllocaInst *srcAlloca = dyn_cast<AllocaInst>(cpySrc); |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 603 | if (!srcAlloca) |
| 604 | return false; |
| 605 | |
| 606 | // Check that all of src is copied to dest. |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 607 | if (!DL) return false; |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 608 | |
Chris Lattner | b5557a7 | 2009-09-01 17:09:55 +0000 | [diff] [blame] | 609 | ConstantInt *srcArraySize = dyn_cast<ConstantInt>(srcAlloca->getArraySize()); |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 610 | if (!srcArraySize) |
| 611 | return false; |
| 612 | |
Rafael Espindola | 37dc9e1 | 2014-02-21 00:06:31 +0000 | [diff] [blame] | 613 | uint64_t srcSize = DL->getTypeAllocSize(srcAlloca->getAllocatedType()) * |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 614 | srcArraySize->getZExtValue(); |
| 615 | |
Owen Anderson | 18e4fed | 2010-10-15 22:52:12 +0000 | [diff] [blame] | 616 | if (cpyLen < srcSize) |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 617 | return false; |
| 618 | |
| 619 | // Check that accessing the first srcSize bytes of dest will not cause a |
| 620 | // trap. Otherwise the transform is invalid since it might cause a trap |
| 621 | // to occur earlier than it otherwise would. |
Chris Lattner | b5557a7 | 2009-09-01 17:09:55 +0000 | [diff] [blame] | 622 | if (AllocaInst *A = dyn_cast<AllocaInst>(cpyDest)) { |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 623 | // The destination is an alloca. Check it is larger than srcSize. |
Chris Lattner | b5557a7 | 2009-09-01 17:09:55 +0000 | [diff] [blame] | 624 | ConstantInt *destArraySize = dyn_cast<ConstantInt>(A->getArraySize()); |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 625 | if (!destArraySize) |
| 626 | return false; |
| 627 | |
Rafael Espindola | 37dc9e1 | 2014-02-21 00:06:31 +0000 | [diff] [blame] | 628 | uint64_t destSize = DL->getTypeAllocSize(A->getAllocatedType()) * |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 629 | destArraySize->getZExtValue(); |
| 630 | |
| 631 | if (destSize < srcSize) |
| 632 | return false; |
Chris Lattner | b5557a7 | 2009-09-01 17:09:55 +0000 | [diff] [blame] | 633 | } else if (Argument *A = dyn_cast<Argument>(cpyDest)) { |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 634 | // If the destination is an sret parameter then only accesses that are |
| 635 | // outside of the returned struct type can trap. |
| 636 | if (!A->hasStructRetAttr()) |
| 637 | return false; |
| 638 | |
Chris Lattner | 229907c | 2011-07-18 04:54:35 +0000 | [diff] [blame] | 639 | Type *StructTy = cast<PointerType>(A->getType())->getElementType(); |
Shuxin Yang | 140d592 | 2013-06-08 04:56:05 +0000 | [diff] [blame] | 640 | if (!StructTy->isSized()) { |
| 641 | // The call may never return and hence the copy-instruction may never |
| 642 | // be executed, and therefore it's not safe to say "the destination |
| 643 | // has at least <cpyLen> bytes, as implied by the copy-instruction", |
| 644 | return false; |
| 645 | } |
| 646 | |
Rafael Espindola | 37dc9e1 | 2014-02-21 00:06:31 +0000 | [diff] [blame] | 647 | uint64_t destSize = DL->getTypeAllocSize(StructTy); |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 648 | if (destSize < srcSize) |
| 649 | return false; |
| 650 | } else { |
| 651 | return false; |
| 652 | } |
| 653 | |
Duncan Sands | 933db77 | 2012-10-05 07:29:46 +0000 | [diff] [blame] | 654 | // Check that dest points to memory that is at least as aligned as src. |
| 655 | unsigned srcAlign = srcAlloca->getAlignment(); |
| 656 | if (!srcAlign) |
Rafael Espindola | 37dc9e1 | 2014-02-21 00:06:31 +0000 | [diff] [blame] | 657 | srcAlign = DL->getABITypeAlignment(srcAlloca->getAllocatedType()); |
Duncan Sands | 933db77 | 2012-10-05 07:29:46 +0000 | [diff] [blame] | 658 | bool isDestSufficientlyAligned = srcAlign <= cpyAlign; |
| 659 | // If dest is not aligned enough and we can't increase its alignment then |
| 660 | // bail out. |
| 661 | if (!isDestSufficientlyAligned && !isa<AllocaInst>(cpyDest)) |
| 662 | return false; |
| 663 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 664 | // Check that src is not accessed except via the call and the memcpy. This |
| 665 | // guarantees that it holds only undefined values when passed in (so the final |
| 666 | // memcpy can be dropped), that it is not read or written between the call and |
| 667 | // the memcpy, and that writing beyond the end of it is undefined. |
Chandler Carruth | cdf4788 | 2014-03-09 03:16:01 +0000 | [diff] [blame] | 668 | SmallVector<User*, 8> srcUseList(srcAlloca->user_begin(), |
| 669 | srcAlloca->user_end()); |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 670 | while (!srcUseList.empty()) { |
Chandler Carruth | cdf4788 | 2014-03-09 03:16:01 +0000 | [diff] [blame] | 671 | User *U = srcUseList.pop_back_val(); |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 672 | |
Chandler Carruth | cdf4788 | 2014-03-09 03:16:01 +0000 | [diff] [blame] | 673 | if (isa<BitCastInst>(U) || isa<AddrSpaceCastInst>(U)) { |
| 674 | for (User *UU : U->users()) |
| 675 | srcUseList.push_back(UU); |
| 676 | } else if (GetElementPtrInst *G = dyn_cast<GetElementPtrInst>(U)) { |
Owen Anderson | 38099c1 | 2008-06-01 22:26:26 +0000 | [diff] [blame] | 677 | if (G->hasAllZeroIndices()) |
Chandler Carruth | cdf4788 | 2014-03-09 03:16:01 +0000 | [diff] [blame] | 678 | for (User *UU : U->users()) |
| 679 | srcUseList.push_back(UU); |
Owen Anderson | 38099c1 | 2008-06-01 22:26:26 +0000 | [diff] [blame] | 680 | else |
| 681 | return false; |
Nick Lewycky | fc243d5 | 2014-09-01 06:03:11 +0000 | [diff] [blame] | 682 | } else if (const IntrinsicInst *IT = dyn_cast<IntrinsicInst>(U)) { |
| 683 | if (IT->getIntrinsicID() != Intrinsic::lifetime_start && |
| 684 | IT->getIntrinsicID() != Intrinsic::lifetime_end) |
| 685 | continue; |
Chandler Carruth | cdf4788 | 2014-03-09 03:16:01 +0000 | [diff] [blame] | 686 | } else if (U != C && U != cpy) { |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 687 | return false; |
| 688 | } |
| 689 | } |
| 690 | |
Nick Lewycky | 703e488 | 2014-07-14 18:52:02 +0000 | [diff] [blame] | 691 | // Check that src isn't captured by the called function since the |
| 692 | // transformation can cause aliasing issues in that case. |
| 693 | for (unsigned i = 0, e = CS.arg_size(); i != e; ++i) |
| 694 | if (CS.getArgument(i) == cpySrc && !CS.doesNotCapture(i)) |
| 695 | return false; |
| 696 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 697 | // Since we're changing the parameter to the callsite, we need to make sure |
| 698 | // that what would be the new parameter dominates the callsite. |
Chandler Carruth | 7352302 | 2014-01-13 13:07:17 +0000 | [diff] [blame] | 699 | DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); |
Chris Lattner | b5557a7 | 2009-09-01 17:09:55 +0000 | [diff] [blame] | 700 | if (Instruction *cpyDestInst = dyn_cast<Instruction>(cpyDest)) |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 701 | if (!DT.dominates(cpyDestInst, C)) |
| 702 | return false; |
| 703 | |
| 704 | // In addition to knowing that the call does not access src in some |
| 705 | // unexpected manner, for example via a global, which we deduce from |
| 706 | // the use analysis, we also need to know that it does not sneakily |
| 707 | // access dest. We rely on AA to figure this out for us. |
Chris Lattner | b5557a7 | 2009-09-01 17:09:55 +0000 | [diff] [blame] | 708 | AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); |
Chad Rosier | a968caf | 2012-05-14 20:35:04 +0000 | [diff] [blame] | 709 | AliasAnalysis::ModRefResult MR = AA.getModRefInfo(C, cpyDest, srcSize); |
| 710 | // If necessary, perform additional analysis. |
| 711 | if (MR != AliasAnalysis::NoModRef) |
| 712 | MR = AA.callCapturesBefore(C, cpyDest, srcSize, &DT); |
| 713 | if (MR != AliasAnalysis::NoModRef) |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 714 | return false; |
| 715 | |
| 716 | // All the checks have passed, so do the transformation. |
Owen Anderson | d071a87 | 2008-06-01 21:52:16 +0000 | [diff] [blame] | 717 | bool changedArgument = false; |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 718 | for (unsigned i = 0; i < CS.arg_size(); ++i) |
Owen Anderson | 38099c1 | 2008-06-01 22:26:26 +0000 | [diff] [blame] | 719 | if (CS.getArgument(i)->stripPointerCasts() == cpySrc) { |
Duncan Sands | a6d2001 | 2012-10-04 13:53:21 +0000 | [diff] [blame] | 720 | Value *Dest = cpySrc->getType() == cpyDest->getType() ? cpyDest |
| 721 | : CastInst::CreatePointerCast(cpyDest, cpySrc->getType(), |
| 722 | cpyDest->getName(), C); |
Owen Anderson | d071a87 | 2008-06-01 21:52:16 +0000 | [diff] [blame] | 723 | changedArgument = true; |
Duncan Sands | a6d2001 | 2012-10-04 13:53:21 +0000 | [diff] [blame] | 724 | if (CS.getArgument(i)->getType() == Dest->getType()) |
| 725 | CS.setArgument(i, Dest); |
Chris Lattner | b5557a7 | 2009-09-01 17:09:55 +0000 | [diff] [blame] | 726 | else |
Duncan Sands | a6d2001 | 2012-10-04 13:53:21 +0000 | [diff] [blame] | 727 | CS.setArgument(i, CastInst::CreatePointerCast(Dest, |
| 728 | CS.getArgument(i)->getType(), Dest->getName(), C)); |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 729 | } |
| 730 | |
Owen Anderson | d071a87 | 2008-06-01 21:52:16 +0000 | [diff] [blame] | 731 | if (!changedArgument) |
| 732 | return false; |
| 733 | |
Duncan Sands | c6ada69 | 2012-10-04 10:54:40 +0000 | [diff] [blame] | 734 | // If the destination wasn't sufficiently aligned then increase its alignment. |
| 735 | if (!isDestSufficientlyAligned) { |
| 736 | assert(isa<AllocaInst>(cpyDest) && "Can only increase alloca alignment!"); |
| 737 | cast<AllocaInst>(cpyDest)->setAlignment(srcAlign); |
| 738 | } |
| 739 | |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 740 | // Drop any cached information about the call, because we may have changed |
| 741 | // its dependence information by changing its parameter. |
Chris Lattner | 58f9f58 | 2010-11-21 00:28:59 +0000 | [diff] [blame] | 742 | MD->removeInstruction(C); |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 743 | |
Chris Lattner | 58f9f58 | 2010-11-21 00:28:59 +0000 | [diff] [blame] | 744 | // Remove the memcpy. |
| 745 | MD->removeInstruction(cpy); |
Dan Gohman | d2d1ae1 | 2010-06-22 15:08:57 +0000 | [diff] [blame] | 746 | ++NumMemCpyInstr; |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 747 | |
| 748 | return true; |
| 749 | } |
| 750 | |
Chris Lattner | 7e9b2ea | 2010-11-18 07:02:37 +0000 | [diff] [blame] | 751 | /// processMemCpyMemCpyDependence - We've found that the (upward scanning) |
| 752 | /// memory dependence of memcpy 'M' is the memcpy 'MDep'. Try to simplify M to |
| 753 | /// copy from MDep's input if we can. MSize is the size of M's copy. |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 754 | /// |
Chris Lattner | 7e9b2ea | 2010-11-18 07:02:37 +0000 | [diff] [blame] | 755 | bool MemCpyOpt::processMemCpyMemCpyDependence(MemCpyInst *M, MemCpyInst *MDep, |
| 756 | uint64_t MSize) { |
| 757 | // We can only transforms memcpy's where the dest of one is the source of the |
| 758 | // other. |
Chris Lattner | 58f9f58 | 2010-11-21 00:28:59 +0000 | [diff] [blame] | 759 | if (M->getSource() != MDep->getDest() || MDep->isVolatile()) |
Chris Lattner | 7e9b2ea | 2010-11-18 07:02:37 +0000 | [diff] [blame] | 760 | return false; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 761 | |
Chris Lattner | fd51c52 | 2010-12-09 07:39:50 +0000 | [diff] [blame] | 762 | // If dep instruction is reading from our current input, then it is a noop |
| 763 | // transfer and substituting the input won't change this instruction. Just |
| 764 | // ignore the input and let someone else zap MDep. This handles cases like: |
| 765 | // memcpy(a <- a) |
| 766 | // memcpy(b <- a) |
| 767 | if (M->getSource() == MDep->getSource()) |
| 768 | return false; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 769 | |
Chris Lattner | 0ab5e2c | 2011-04-15 05:18:47 +0000 | [diff] [blame] | 770 | // Second, the length of the memcpy's must be the same, or the preceding one |
Chris Lattner | 7e9b2ea | 2010-11-18 07:02:37 +0000 | [diff] [blame] | 771 | // must be larger than the following one. |
Dan Gohman | 19e30d5 | 2011-01-21 22:07:57 +0000 | [diff] [blame] | 772 | ConstantInt *MDepLen = dyn_cast<ConstantInt>(MDep->getLength()); |
| 773 | ConstantInt *MLen = dyn_cast<ConstantInt>(M->getLength()); |
| 774 | if (!MDepLen || !MLen || MDepLen->getZExtValue() < MLen->getZExtValue()) |
| 775 | return false; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 776 | |
Chris Lattner | 58f9f58 | 2010-11-21 00:28:59 +0000 | [diff] [blame] | 777 | AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); |
Chris Lattner | 5957229 | 2010-11-21 08:06:10 +0000 | [diff] [blame] | 778 | |
| 779 | // Verify that the copied-from memory doesn't change in between the two |
| 780 | // transfers. For example, in: |
| 781 | // memcpy(a <- b) |
| 782 | // *b = 42; |
| 783 | // memcpy(c <- a) |
| 784 | // It would be invalid to transform the second memcpy into memcpy(c <- b). |
| 785 | // |
| 786 | // TODO: If the code between M and MDep is transparent to the destination "c", |
| 787 | // then we could still perform the xform by moving M up to the first memcpy. |
| 788 | // |
| 789 | // NOTE: This is conservative, it will stop on any read from the source loc, |
| 790 | // not just the defining memcpy. |
| 791 | MemDepResult SourceDep = |
| 792 | MD->getPointerDependencyFrom(AA.getLocationForSource(MDep), |
| 793 | false, M, M->getParent()); |
| 794 | if (!SourceDep.isClobber() || SourceDep.getInst() != MDep) |
| 795 | return false; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 796 | |
Chris Lattner | 731caac | 2010-11-18 08:00:57 +0000 | [diff] [blame] | 797 | // If the dest of the second might alias the source of the first, then the |
| 798 | // source and dest might overlap. We still want to eliminate the intermediate |
| 799 | // value, but we have to generate a memmove instead of memcpy. |
Chris Lattner | 6cf8d6c | 2010-12-26 22:57:41 +0000 | [diff] [blame] | 800 | bool UseMemMove = false; |
| 801 | if (!AA.isNoAlias(AA.getLocationForDest(M), AA.getLocationForSource(MDep))) |
| 802 | UseMemMove = true; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 803 | |
Chris Lattner | 58f9f58 | 2010-11-21 00:28:59 +0000 | [diff] [blame] | 804 | // If all checks passed, then we can transform M. |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 805 | |
Chris Lattner | 7e9b2ea | 2010-11-18 07:02:37 +0000 | [diff] [blame] | 806 | // Make sure to use the lesser of the alignment of the source and the dest |
| 807 | // since we're changing where we're reading from, but don't want to increase |
| 808 | // the alignment past what can be read from or written to. |
| 809 | // TODO: Is this worth it if we're creating a less aligned memcpy? For |
| 810 | // example we could be moving from movaps -> movq on x86. |
Chris Lattner | 1385dff | 2010-11-18 08:07:09 +0000 | [diff] [blame] | 811 | unsigned Align = std::min(MDep->getAlignment(), M->getAlignment()); |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 812 | |
Chris Lattner | 6cf8d6c | 2010-12-26 22:57:41 +0000 | [diff] [blame] | 813 | IRBuilder<> Builder(M); |
| 814 | if (UseMemMove) |
| 815 | Builder.CreateMemMove(M->getRawDest(), MDep->getRawSource(), M->getLength(), |
| 816 | Align, M->isVolatile()); |
| 817 | else |
| 818 | Builder.CreateMemCpy(M->getRawDest(), MDep->getRawSource(), M->getLength(), |
| 819 | Align, M->isVolatile()); |
Chris Lattner | 1385dff | 2010-11-18 08:07:09 +0000 | [diff] [blame] | 820 | |
Chris Lattner | 5957229 | 2010-11-21 08:06:10 +0000 | [diff] [blame] | 821 | // Remove the instruction we're replacing. |
Chris Lattner | 58f9f58 | 2010-11-21 00:28:59 +0000 | [diff] [blame] | 822 | MD->removeInstruction(M); |
Chris Lattner | 1385dff | 2010-11-18 08:07:09 +0000 | [diff] [blame] | 823 | M->eraseFromParent(); |
| 824 | ++NumMemCpyInstr; |
| 825 | return true; |
Chris Lattner | 7e9b2ea | 2010-11-18 07:02:37 +0000 | [diff] [blame] | 826 | } |
| 827 | |
| 828 | |
Gabor Greif | 62f0aac | 2010-07-28 22:50:26 +0000 | [diff] [blame] | 829 | /// processMemCpy - perform simplification of memcpy's. If we have memcpy A |
| 830 | /// which copies X to Y, and memcpy B which copies Y to Z, then we can rewrite |
| 831 | /// B to be a memcpy from X to Z (or potentially a memmove, depending on |
| 832 | /// circumstances). This allows later passes to remove the first memcpy |
| 833 | /// altogether. |
Chris Lattner | b5557a7 | 2009-09-01 17:09:55 +0000 | [diff] [blame] | 834 | bool MemCpyOpt::processMemCpy(MemCpyInst *M) { |
Nick Lewycky | 00703e7 | 2014-02-04 00:18:54 +0000 | [diff] [blame] | 835 | // We can only optimize non-volatile memcpy's. |
| 836 | if (M->isVolatile()) return false; |
Owen Anderson | 18e4fed | 2010-10-15 22:52:12 +0000 | [diff] [blame] | 837 | |
Chris Lattner | bc4457e | 2010-12-09 07:45:45 +0000 | [diff] [blame] | 838 | // If the source and destination of the memcpy are the same, then zap it. |
| 839 | if (M->getSource() == M->getDest()) { |
| 840 | MD->removeInstruction(M); |
| 841 | M->eraseFromParent(); |
| 842 | return false; |
| 843 | } |
Benjamin Kramer | ea9152e | 2010-12-24 21:17:12 +0000 | [diff] [blame] | 844 | |
| 845 | // If copying from a constant, try to turn the memcpy into a memset. |
Benjamin Kramer | b90b2f0 | 2010-12-24 22:23:59 +0000 | [diff] [blame] | 846 | if (GlobalVariable *GV = dyn_cast<GlobalVariable>(M->getSource())) |
Benjamin Kramer | 30342fb | 2010-12-26 15:23:45 +0000 | [diff] [blame] | 847 | if (GV->isConstant() && GV->hasDefinitiveInitializer()) |
Benjamin Kramer | b90b2f0 | 2010-12-24 22:23:59 +0000 | [diff] [blame] | 848 | if (Value *ByteVal = isBytewiseValue(GV->getInitializer())) { |
Chris Lattner | 6cf8d6c | 2010-12-26 22:57:41 +0000 | [diff] [blame] | 849 | IRBuilder<> Builder(M); |
Nick Lewycky | 00703e7 | 2014-02-04 00:18:54 +0000 | [diff] [blame] | 850 | Builder.CreateMemSet(M->getRawDest(), ByteVal, M->getLength(), |
Chris Lattner | 6cf8d6c | 2010-12-26 22:57:41 +0000 | [diff] [blame] | 851 | M->getAlignment(), false); |
Benjamin Kramer | b90b2f0 | 2010-12-24 22:23:59 +0000 | [diff] [blame] | 852 | MD->removeInstruction(M); |
| 853 | M->eraseFromParent(); |
| 854 | ++NumCpyToSet; |
| 855 | return true; |
| 856 | } |
Benjamin Kramer | ea9152e | 2010-12-24 21:17:12 +0000 | [diff] [blame] | 857 | |
Nick Lewycky | 00703e7 | 2014-02-04 00:18:54 +0000 | [diff] [blame] | 858 | // The optimizations after this point require the memcpy size. |
| 859 | ConstantInt *CopySize = dyn_cast<ConstantInt>(M->getLength()); |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 860 | if (!CopySize) return false; |
Nick Lewycky | 00703e7 | 2014-02-04 00:18:54 +0000 | [diff] [blame] | 861 | |
Nick Lewycky | 9938494 | 2014-02-06 06:29:19 +0000 | [diff] [blame] | 862 | // The are three possible optimizations we can do for memcpy: |
Chris Lattner | b5557a7 | 2009-09-01 17:09:55 +0000 | [diff] [blame] | 863 | // a) memcpy-memcpy xform which exposes redundance for DSE. |
| 864 | // b) call-memcpy xform for return slot optimization. |
Nick Lewycky | 77d5fb4 | 2014-03-26 23:45:15 +0000 | [diff] [blame] | 865 | // c) memcpy from freshly alloca'd space or space that has just started its |
| 866 | // lifetime copies undefined data, and we can therefore eliminate the |
| 867 | // memcpy in favor of the data that was already at the destination. |
Chris Lattner | 58f9f58 | 2010-11-21 00:28:59 +0000 | [diff] [blame] | 868 | MemDepResult DepInfo = MD->getDependency(M); |
Nick Lewycky | 0a7e9cc | 2011-10-16 20:13:32 +0000 | [diff] [blame] | 869 | if (DepInfo.isClobber()) { |
| 870 | if (CallInst *C = dyn_cast<CallInst>(DepInfo.getInst())) { |
| 871 | if (performCallSlotOptzn(M, M->getDest(), M->getSource(), |
Duncan Sands | c6ada69 | 2012-10-04 10:54:40 +0000 | [diff] [blame] | 872 | CopySize->getZExtValue(), M->getAlignment(), |
| 873 | C)) { |
Nick Lewycky | 0a7e9cc | 2011-10-16 20:13:32 +0000 | [diff] [blame] | 874 | MD->removeInstruction(M); |
| 875 | M->eraseFromParent(); |
| 876 | return true; |
| 877 | } |
Chris Lattner | bc4457e | 2010-12-09 07:45:45 +0000 | [diff] [blame] | 878 | } |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 879 | } |
Ahmed Charles | 32e983e | 2012-02-13 06:30:56 +0000 | [diff] [blame] | 880 | |
| 881 | AliasAnalysis::Location SrcLoc = AliasAnalysis::getLocationForSource(M); |
Nick Lewycky | 0a7e9cc | 2011-10-16 20:13:32 +0000 | [diff] [blame] | 882 | MemDepResult SrcDepInfo = MD->getPointerDependencyFrom(SrcLoc, true, |
| 883 | M, M->getParent()); |
| 884 | if (SrcDepInfo.isClobber()) { |
| 885 | if (MemCpyInst *MDep = dyn_cast<MemCpyInst>(SrcDepInfo.getInst())) |
| 886 | return processMemCpyMemCpyDependence(M, MDep, CopySize->getZExtValue()); |
Nick Lewycky | 9938494 | 2014-02-06 06:29:19 +0000 | [diff] [blame] | 887 | } else if (SrcDepInfo.isDef()) { |
Nick Lewycky | 77d5fb4 | 2014-03-26 23:45:15 +0000 | [diff] [blame] | 888 | Instruction *I = SrcDepInfo.getInst(); |
| 889 | bool hasUndefContents = false; |
| 890 | |
| 891 | if (isa<AllocaInst>(I)) { |
| 892 | hasUndefContents = true; |
| 893 | } else if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) { |
| 894 | if (II->getIntrinsicID() == Intrinsic::lifetime_start) |
| 895 | if (ConstantInt *LTSize = dyn_cast<ConstantInt>(II->getArgOperand(0))) |
| 896 | if (LTSize->getZExtValue() >= CopySize->getZExtValue()) |
| 897 | hasUndefContents = true; |
| 898 | } |
| 899 | |
| 900 | if (hasUndefContents) { |
Nick Lewycky | 9938494 | 2014-02-06 06:29:19 +0000 | [diff] [blame] | 901 | MD->removeInstruction(M); |
| 902 | M->eraseFromParent(); |
| 903 | ++NumMemCpyInstr; |
| 904 | return true; |
| 905 | } |
Nick Lewycky | 0a7e9cc | 2011-10-16 20:13:32 +0000 | [diff] [blame] | 906 | } |
| 907 | |
Owen Anderson | ad5367f | 2008-04-29 21:51:00 +0000 | [diff] [blame] | 908 | return false; |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 909 | } |
| 910 | |
Chris Lattner | 1145e33 | 2009-09-01 17:56:32 +0000 | [diff] [blame] | 911 | /// processMemMove - Transforms memmove calls to memcpy calls when the src/dst |
| 912 | /// are guaranteed not to alias. |
| 913 | bool MemCpyOpt::processMemMove(MemMoveInst *M) { |
| 914 | AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); |
| 915 | |
Chris Lattner | 23f61a0 | 2011-05-01 18:27:11 +0000 | [diff] [blame] | 916 | if (!TLI->has(LibFunc::memmove)) |
| 917 | return false; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 918 | |
Chris Lattner | 1145e33 | 2009-09-01 17:56:32 +0000 | [diff] [blame] | 919 | // See if the pointers alias. |
Chris Lattner | 6cf8d6c | 2010-12-26 22:57:41 +0000 | [diff] [blame] | 920 | if (!AA.isNoAlias(AA.getLocationForDest(M), AA.getLocationForSource(M))) |
Chris Lattner | 1145e33 | 2009-09-01 17:56:32 +0000 | [diff] [blame] | 921 | return false; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 922 | |
David Greene | 2419923 | 2010-01-05 01:27:47 +0000 | [diff] [blame] | 923 | DEBUG(dbgs() << "MemCpyOpt: Optimizing memmove -> memcpy: " << *M << "\n"); |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 924 | |
Chris Lattner | 1145e33 | 2009-09-01 17:56:32 +0000 | [diff] [blame] | 925 | // If not, then we know we can transform this. |
| 926 | Module *Mod = M->getParent()->getParent()->getParent(); |
Jay Foad | b804a2b | 2011-07-12 14:06:48 +0000 | [diff] [blame] | 927 | Type *ArgTys[3] = { M->getRawDest()->getType(), |
| 928 | M->getRawSource()->getType(), |
| 929 | M->getLength()->getType() }; |
Gabor Greif | 3e44ea1 | 2010-07-22 10:37:47 +0000 | [diff] [blame] | 930 | M->setCalledFunction(Intrinsic::getDeclaration(Mod, Intrinsic::memcpy, |
Benjamin Kramer | e6e1933 | 2011-07-14 17:45:39 +0000 | [diff] [blame] | 931 | ArgTys)); |
Duncan Sands | 0edc710 | 2009-09-03 13:37:16 +0000 | [diff] [blame] | 932 | |
Chris Lattner | 1145e33 | 2009-09-01 17:56:32 +0000 | [diff] [blame] | 933 | // MemDep may have over conservative information about this instruction, just |
| 934 | // conservatively flush it from the cache. |
Chris Lattner | 58f9f58 | 2010-11-21 00:28:59 +0000 | [diff] [blame] | 935 | MD->removeInstruction(M); |
Duncan Sands | 0edc710 | 2009-09-03 13:37:16 +0000 | [diff] [blame] | 936 | |
| 937 | ++NumMoveToCpy; |
Chris Lattner | 1145e33 | 2009-09-01 17:56:32 +0000 | [diff] [blame] | 938 | return true; |
| 939 | } |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 940 | |
Chris Lattner | 58f9f58 | 2010-11-21 00:28:59 +0000 | [diff] [blame] | 941 | /// processByValArgument - This is called on every byval argument in call sites. |
| 942 | bool MemCpyOpt::processByValArgument(CallSite CS, unsigned ArgNo) { |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 943 | if (!DL) return false; |
Chris Lattner | 1145e33 | 2009-09-01 17:56:32 +0000 | [diff] [blame] | 944 | |
Chris Lattner | 5957229 | 2010-11-21 08:06:10 +0000 | [diff] [blame] | 945 | // Find out what feeds this byval argument. |
Chris Lattner | 58f9f58 | 2010-11-21 00:28:59 +0000 | [diff] [blame] | 946 | Value *ByValArg = CS.getArgument(ArgNo); |
Nick Lewycky | c585de6 | 2011-10-12 00:14:31 +0000 | [diff] [blame] | 947 | Type *ByValTy = cast<PointerType>(ByValArg->getType())->getElementType(); |
Rafael Espindola | 37dc9e1 | 2014-02-21 00:06:31 +0000 | [diff] [blame] | 948 | uint64_t ByValSize = DL->getTypeAllocSize(ByValTy); |
Chris Lattner | 5957229 | 2010-11-21 08:06:10 +0000 | [diff] [blame] | 949 | MemDepResult DepInfo = |
| 950 | MD->getPointerDependencyFrom(AliasAnalysis::Location(ByValArg, ByValSize), |
| 951 | true, CS.getInstruction(), |
| 952 | CS.getInstruction()->getParent()); |
Chris Lattner | 58f9f58 | 2010-11-21 00:28:59 +0000 | [diff] [blame] | 953 | if (!DepInfo.isClobber()) |
| 954 | return false; |
| 955 | |
| 956 | // If the byval argument isn't fed by a memcpy, ignore it. If it is fed by |
| 957 | // a memcpy, see if we can byval from the source of the memcpy instead of the |
| 958 | // result. |
| 959 | MemCpyInst *MDep = dyn_cast<MemCpyInst>(DepInfo.getInst()); |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 960 | if (!MDep || MDep->isVolatile() || |
Chris Lattner | 58f9f58 | 2010-11-21 00:28:59 +0000 | [diff] [blame] | 961 | ByValArg->stripPointerCasts() != MDep->getDest()) |
| 962 | return false; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 963 | |
Chris Lattner | 58f9f58 | 2010-11-21 00:28:59 +0000 | [diff] [blame] | 964 | // The length of the memcpy must be larger or equal to the size of the byval. |
Chris Lattner | 58f9f58 | 2010-11-21 00:28:59 +0000 | [diff] [blame] | 965 | ConstantInt *C1 = dyn_cast<ConstantInt>(MDep->getLength()); |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 966 | if (!C1 || C1->getValue().getZExtValue() < ByValSize) |
Chris Lattner | 58f9f58 | 2010-11-21 00:28:59 +0000 | [diff] [blame] | 967 | return false; |
| 968 | |
Chris Lattner | 83791ce | 2011-05-23 00:03:39 +0000 | [diff] [blame] | 969 | // Get the alignment of the byval. If the call doesn't specify the alignment, |
| 970 | // then it is some target specific value that we can't know. |
Chris Lattner | 58f9f58 | 2010-11-21 00:28:59 +0000 | [diff] [blame] | 971 | unsigned ByValAlign = CS.getParamAlignment(ArgNo+1); |
Chris Lattner | 83791ce | 2011-05-23 00:03:39 +0000 | [diff] [blame] | 972 | if (ByValAlign == 0) return false; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 973 | |
Chris Lattner | 83791ce | 2011-05-23 00:03:39 +0000 | [diff] [blame] | 974 | // If it is greater than the memcpy, then we check to see if we can force the |
| 975 | // source of the memcpy to the alignment we need. If we fail, we bail out. |
| 976 | if (MDep->getAlignment() < ByValAlign && |
Rafael Espindola | 37dc9e1 | 2014-02-21 00:06:31 +0000 | [diff] [blame] | 977 | getOrEnforceKnownAlignment(MDep->getSource(),ByValAlign, DL) < ByValAlign) |
Chris Lattner | 83791ce | 2011-05-23 00:03:39 +0000 | [diff] [blame] | 978 | return false; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 979 | |
Chris Lattner | 58f9f58 | 2010-11-21 00:28:59 +0000 | [diff] [blame] | 980 | // Verify that the copied-from memory doesn't change in between the memcpy and |
| 981 | // the byval call. |
| 982 | // memcpy(a <- b) |
| 983 | // *b = 42; |
| 984 | // foo(*a) |
| 985 | // It would be invalid to transform the second memcpy into foo(*b). |
Chris Lattner | 5957229 | 2010-11-21 08:06:10 +0000 | [diff] [blame] | 986 | // |
| 987 | // NOTE: This is conservative, it will stop on any read from the source loc, |
| 988 | // not just the defining memcpy. |
| 989 | MemDepResult SourceDep = |
| 990 | MD->getPointerDependencyFrom(AliasAnalysis::getLocationForSource(MDep), |
| 991 | false, CS.getInstruction(), MDep->getParent()); |
| 992 | if (!SourceDep.isClobber() || SourceDep.getInst() != MDep) |
| 993 | return false; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 994 | |
Chris Lattner | 58f9f58 | 2010-11-21 00:28:59 +0000 | [diff] [blame] | 995 | Value *TmpCast = MDep->getSource(); |
| 996 | if (MDep->getSource()->getType() != ByValArg->getType()) |
| 997 | TmpCast = new BitCastInst(MDep->getSource(), ByValArg->getType(), |
| 998 | "tmpcast", CS.getInstruction()); |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 999 | |
Chris Lattner | 58f9f58 | 2010-11-21 00:28:59 +0000 | [diff] [blame] | 1000 | DEBUG(dbgs() << "MemCpyOpt: Forwarding memcpy to byval:\n" |
| 1001 | << " " << *MDep << "\n" |
| 1002 | << " " << *CS.getInstruction() << "\n"); |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 1003 | |
Chris Lattner | 58f9f58 | 2010-11-21 00:28:59 +0000 | [diff] [blame] | 1004 | // Otherwise we're good! Update the byval argument. |
| 1005 | CS.setArgument(ArgNo, TmpCast); |
| 1006 | ++NumMemCpyInstr; |
| 1007 | return true; |
| 1008 | } |
| 1009 | |
| 1010 | /// iterateOnFunction - Executes one iteration of MemCpyOpt. |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 1011 | bool MemCpyOpt::iterateOnFunction(Function &F) { |
Chris Lattner | b5557a7 | 2009-09-01 17:09:55 +0000 | [diff] [blame] | 1012 | bool MadeChange = false; |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 1013 | |
Chris Lattner | b5557a7 | 2009-09-01 17:09:55 +0000 | [diff] [blame] | 1014 | // Walk all instruction in the function. |
Owen Anderson | 6a7355c | 2008-04-21 07:45:10 +0000 | [diff] [blame] | 1015 | for (Function::iterator BB = F.begin(), BBE = F.end(); BB != BBE; ++BB) { |
Chris Lattner | 58f9f58 | 2010-11-21 00:28:59 +0000 | [diff] [blame] | 1016 | for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) { |
Chris Lattner | b5557a7 | 2009-09-01 17:09:55 +0000 | [diff] [blame] | 1017 | // Avoid invalidating the iterator. |
| 1018 | Instruction *I = BI++; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 1019 | |
Chris Lattner | 58f9f58 | 2010-11-21 00:28:59 +0000 | [diff] [blame] | 1020 | bool RepeatInstruction = false; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 1021 | |
Owen Anderson | 6a7355c | 2008-04-21 07:45:10 +0000 | [diff] [blame] | 1022 | if (StoreInst *SI = dyn_cast<StoreInst>(I)) |
Chris Lattner | b5557a7 | 2009-09-01 17:09:55 +0000 | [diff] [blame] | 1023 | MadeChange |= processStore(SI, BI); |
Chris Lattner | 9a1d63b | 2011-01-08 21:19:19 +0000 | [diff] [blame] | 1024 | else if (MemSetInst *M = dyn_cast<MemSetInst>(I)) |
| 1025 | RepeatInstruction = processMemSet(M, BI); |
| 1026 | else if (MemCpyInst *M = dyn_cast<MemCpyInst>(I)) |
Chris Lattner | 58f9f58 | 2010-11-21 00:28:59 +0000 | [diff] [blame] | 1027 | RepeatInstruction = processMemCpy(M); |
Chris Lattner | 9a1d63b | 2011-01-08 21:19:19 +0000 | [diff] [blame] | 1028 | else if (MemMoveInst *M = dyn_cast<MemMoveInst>(I)) |
Chris Lattner | 58f9f58 | 2010-11-21 00:28:59 +0000 | [diff] [blame] | 1029 | RepeatInstruction = processMemMove(M); |
Chris Lattner | 9a1d63b | 2011-01-08 21:19:19 +0000 | [diff] [blame] | 1030 | else if (CallSite CS = (Value*)I) { |
Chris Lattner | 58f9f58 | 2010-11-21 00:28:59 +0000 | [diff] [blame] | 1031 | for (unsigned i = 0, e = CS.arg_size(); i != e; ++i) |
Nick Lewycky | 612d70b | 2011-11-20 19:09:04 +0000 | [diff] [blame] | 1032 | if (CS.isByValArgument(i)) |
Chris Lattner | 58f9f58 | 2010-11-21 00:28:59 +0000 | [diff] [blame] | 1033 | MadeChange |= processByValArgument(CS, i); |
| 1034 | } |
| 1035 | |
| 1036 | // Reprocess the instruction if desired. |
| 1037 | if (RepeatInstruction) { |
Chris Lattner | 7d6433a | 2011-01-08 22:19:21 +0000 | [diff] [blame] | 1038 | if (BI != BB->begin()) --BI; |
Chris Lattner | 58f9f58 | 2010-11-21 00:28:59 +0000 | [diff] [blame] | 1039 | MadeChange = true; |
Chris Lattner | 1145e33 | 2009-09-01 17:56:32 +0000 | [diff] [blame] | 1040 | } |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 1041 | } |
| 1042 | } |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 1043 | |
Chris Lattner | b5557a7 | 2009-09-01 17:09:55 +0000 | [diff] [blame] | 1044 | return MadeChange; |
Owen Anderson | ef9a6fd | 2008-04-09 08:23:16 +0000 | [diff] [blame] | 1045 | } |
Chris Lattner | b5557a7 | 2009-09-01 17:09:55 +0000 | [diff] [blame] | 1046 | |
| 1047 | // MemCpyOpt::runOnFunction - This is the main transformation entry point for a |
| 1048 | // function. |
| 1049 | // |
| 1050 | bool MemCpyOpt::runOnFunction(Function &F) { |
Paul Robinson | af4e64d | 2014-02-06 00:07:05 +0000 | [diff] [blame] | 1051 | if (skipOptnoneFunction(F)) |
| 1052 | return false; |
| 1053 | |
Chris Lattner | b5557a7 | 2009-09-01 17:09:55 +0000 | [diff] [blame] | 1054 | bool MadeChange = false; |
Chris Lattner | 58f9f58 | 2010-11-21 00:28:59 +0000 | [diff] [blame] | 1055 | MD = &getAnalysis<MemoryDependenceAnalysis>(); |
Rafael Espindola | 9351251 | 2014-02-25 17:30:31 +0000 | [diff] [blame] | 1056 | DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>(); |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 1057 | DL = DLP ? &DLP->getDataLayout() : nullptr; |
Chris Lattner | 23f61a0 | 2011-05-01 18:27:11 +0000 | [diff] [blame] | 1058 | TLI = &getAnalysis<TargetLibraryInfo>(); |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 1059 | |
Chris Lattner | 23f61a0 | 2011-05-01 18:27:11 +0000 | [diff] [blame] | 1060 | // If we don't have at least memset and memcpy, there is little point of doing |
| 1061 | // anything here. These are required by a freestanding implementation, so if |
| 1062 | // even they are disabled, there is no point in trying hard. |
| 1063 | if (!TLI->has(LibFunc::memset) || !TLI->has(LibFunc::memcpy)) |
| 1064 | return false; |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 1065 | |
Chris Lattner | b5557a7 | 2009-09-01 17:09:55 +0000 | [diff] [blame] | 1066 | while (1) { |
| 1067 | if (!iterateOnFunction(F)) |
| 1068 | break; |
| 1069 | MadeChange = true; |
| 1070 | } |
Nadav Rotem | 465834c | 2012-07-24 10:51:42 +0000 | [diff] [blame] | 1071 | |
Craig Topper | f40110f | 2014-04-25 05:29:35 +0000 | [diff] [blame] | 1072 | MD = nullptr; |
Chris Lattner | b5557a7 | 2009-09-01 17:09:55 +0000 | [diff] [blame] | 1073 | return MadeChange; |
| 1074 | } |