blob: 19a11f9896ed317794443beaf3c20872b5825fad [file] [log] [blame]
Chris Lattnera65e2f72010-01-05 05:57:49 +00001//===- InstCombineLoadStoreAlloca.cpp -------------------------------------===//
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 file implements the visit functions for load, store and alloca.
11//
12//===----------------------------------------------------------------------===//
13
Chandler Carrutha9174582015-01-22 05:25:13 +000014#include "InstCombineInternal.h"
NAKAMURA Takumiec6b1fc2015-12-15 09:37:31 +000015#include "llvm/ADT/SmallString.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000016#include "llvm/ADT/Statistic.h"
Dan Gohman826bdf82010-05-28 16:19:17 +000017#include "llvm/Analysis/Loads.h"
Peter Collingbourneecdd58f2016-10-21 19:59:26 +000018#include "llvm/IR/ConstantRange.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000019#include "llvm/IR/DataLayout.h"
Chandler Carruthbc6378d2014-10-19 10:46:46 +000020#include "llvm/IR/LLVMContext.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000021#include "llvm/IR/IntrinsicInst.h"
Charles Davis33d1dc02015-02-25 05:10:25 +000022#include "llvm/IR/MDBuilder.h"
Chris Lattnera65e2f72010-01-05 05:57:49 +000023#include "llvm/Transforms/Utils/BasicBlockUtils.h"
24#include "llvm/Transforms/Utils/Local.h"
Chris Lattnera65e2f72010-01-05 05:57:49 +000025using namespace llvm;
26
Chandler Carruth964daaa2014-04-22 02:55:47 +000027#define DEBUG_TYPE "instcombine"
28
Chandler Carruthc908ca12012-08-21 08:39:44 +000029STATISTIC(NumDeadStore, "Number of dead stores eliminated");
30STATISTIC(NumGlobalCopies, "Number of allocas copied from constant global");
31
32/// pointsToConstantGlobal - Return true if V (possibly indirectly) points to
33/// some part of a constant global variable. This intentionally only accepts
34/// constant expressions because we can't rewrite arbitrary instructions.
35static bool pointsToConstantGlobal(Value *V) {
36 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(V))
37 return GV->isConstant();
Matt Arsenault607281772014-04-24 00:01:09 +000038
39 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V)) {
Chandler Carruthc908ca12012-08-21 08:39:44 +000040 if (CE->getOpcode() == Instruction::BitCast ||
Matt Arsenault607281772014-04-24 00:01:09 +000041 CE->getOpcode() == Instruction::AddrSpaceCast ||
Chandler Carruthc908ca12012-08-21 08:39:44 +000042 CE->getOpcode() == Instruction::GetElementPtr)
43 return pointsToConstantGlobal(CE->getOperand(0));
Matt Arsenault607281772014-04-24 00:01:09 +000044 }
Chandler Carruthc908ca12012-08-21 08:39:44 +000045 return false;
46}
47
48/// isOnlyCopiedFromConstantGlobal - Recursively walk the uses of a (derived)
49/// pointer to an alloca. Ignore any reads of the pointer, return false if we
50/// see any stores or other unknown uses. If we see pointer arithmetic, keep
51/// track of whether it moves the pointer (with IsOffset) but otherwise traverse
52/// the uses. If we see a memcpy/memmove that targets an unoffseted pointer to
53/// the alloca, and if the source pointer is a pointer to a constant global, we
54/// can optimize this.
55static bool
56isOnlyCopiedFromConstantGlobal(Value *V, MemTransferInst *&TheCopy,
Reid Kleckner813dab22014-07-01 21:36:20 +000057 SmallVectorImpl<Instruction *> &ToDelete) {
Chandler Carruthc908ca12012-08-21 08:39:44 +000058 // We track lifetime intrinsics as we encounter them. If we decide to go
59 // ahead and replace the value with the global, this lets the caller quickly
60 // eliminate the markers.
61
Reid Kleckner813dab22014-07-01 21:36:20 +000062 SmallVector<std::pair<Value *, bool>, 35> ValuesToInspect;
David Majnemer0a16c222016-08-11 21:15:00 +000063 ValuesToInspect.emplace_back(V, false);
Reid Kleckner813dab22014-07-01 21:36:20 +000064 while (!ValuesToInspect.empty()) {
65 auto ValuePair = ValuesToInspect.pop_back_val();
66 const bool IsOffset = ValuePair.second;
67 for (auto &U : ValuePair.first->uses()) {
David Majnemer0a16c222016-08-11 21:15:00 +000068 auto *I = cast<Instruction>(U.getUser());
Chandler Carruthc908ca12012-08-21 08:39:44 +000069
David Majnemer0a16c222016-08-11 21:15:00 +000070 if (auto *LI = dyn_cast<LoadInst>(I)) {
Reid Kleckner813dab22014-07-01 21:36:20 +000071 // Ignore non-volatile loads, they are always ok.
72 if (!LI->isSimple()) return false;
Chandler Carruthc908ca12012-08-21 08:39:44 +000073 continue;
74 }
Reid Kleckner813dab22014-07-01 21:36:20 +000075
76 if (isa<BitCastInst>(I) || isa<AddrSpaceCastInst>(I)) {
77 // If uses of the bitcast are ok, we are ok.
David Majnemer0a16c222016-08-11 21:15:00 +000078 ValuesToInspect.emplace_back(I, IsOffset);
Reid Kleckner813dab22014-07-01 21:36:20 +000079 continue;
80 }
David Majnemer0a16c222016-08-11 21:15:00 +000081 if (auto *GEP = dyn_cast<GetElementPtrInst>(I)) {
Reid Kleckner813dab22014-07-01 21:36:20 +000082 // If the GEP has all zero indices, it doesn't offset the pointer. If it
83 // doesn't, it does.
David Majnemer0a16c222016-08-11 21:15:00 +000084 ValuesToInspect.emplace_back(I, IsOffset || !GEP->hasAllZeroIndices());
Reid Kleckner813dab22014-07-01 21:36:20 +000085 continue;
86 }
87
Benjamin Kramer3a09ef62015-04-10 14:50:08 +000088 if (auto CS = CallSite(I)) {
Reid Kleckner813dab22014-07-01 21:36:20 +000089 // If this is the function being called then we treat it like a load and
90 // ignore it.
91 if (CS.isCallee(&U))
92 continue;
93
David Majnemer02f47872015-12-23 09:58:41 +000094 unsigned DataOpNo = CS.getDataOperandNo(&U);
95 bool IsArgOperand = CS.isArgOperand(&U);
96
Reid Kleckner813dab22014-07-01 21:36:20 +000097 // Inalloca arguments are clobbered by the call.
David Majnemer02f47872015-12-23 09:58:41 +000098 if (IsArgOperand && CS.isInAllocaArgument(DataOpNo))
Reid Kleckner813dab22014-07-01 21:36:20 +000099 return false;
100
101 // If this is a readonly/readnone call site, then we know it is just a
102 // load (but one that potentially returns the value itself), so we can
103 // ignore it if we know that the value isn't captured.
104 if (CS.onlyReadsMemory() &&
David Majnemer02f47872015-12-23 09:58:41 +0000105 (CS.getInstruction()->use_empty() || CS.doesNotCapture(DataOpNo)))
Reid Kleckner813dab22014-07-01 21:36:20 +0000106 continue;
107
108 // If this is being passed as a byval argument, the caller is making a
109 // copy, so it is only a read of the alloca.
David Majnemer02f47872015-12-23 09:58:41 +0000110 if (IsArgOperand && CS.isByValArgument(DataOpNo))
Reid Kleckner813dab22014-07-01 21:36:20 +0000111 continue;
112 }
113
114 // Lifetime intrinsics can be handled by the caller.
115 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) {
116 if (II->getIntrinsicID() == Intrinsic::lifetime_start ||
117 II->getIntrinsicID() == Intrinsic::lifetime_end) {
118 assert(II->use_empty() && "Lifetime markers have no result to use!");
119 ToDelete.push_back(II);
120 continue;
121 }
122 }
123
124 // If this is isn't our memcpy/memmove, reject it as something we can't
125 // handle.
126 MemTransferInst *MI = dyn_cast<MemTransferInst>(I);
127 if (!MI)
128 return false;
129
130 // If the transfer is using the alloca as a source of the transfer, then
131 // ignore it since it is a load (unless the transfer is volatile).
132 if (U.getOperandNo() == 1) {
133 if (MI->isVolatile()) return false;
134 continue;
135 }
136
137 // If we already have seen a copy, reject the second one.
138 if (TheCopy) return false;
139
140 // If the pointer has been offset from the start of the alloca, we can't
141 // safely handle this.
142 if (IsOffset) return false;
143
144 // If the memintrinsic isn't using the alloca as the dest, reject it.
145 if (U.getOperandNo() != 0) return false;
146
147 // If the source of the memcpy/move is not a constant global, reject it.
148 if (!pointsToConstantGlobal(MI->getSource()))
149 return false;
150
151 // Otherwise, the transform is safe. Remember the copy instruction.
152 TheCopy = MI;
Chandler Carruthc908ca12012-08-21 08:39:44 +0000153 }
Chandler Carruthc908ca12012-08-21 08:39:44 +0000154 }
155 return true;
156}
157
158/// isOnlyCopiedFromConstantGlobal - Return true if the specified alloca is only
159/// modified by a copy from a constant global. If we can prove this, we can
160/// replace any uses of the alloca with uses of the global directly.
161static MemTransferInst *
162isOnlyCopiedFromConstantGlobal(AllocaInst *AI,
163 SmallVectorImpl<Instruction *> &ToDelete) {
Craig Topperf40110f2014-04-25 05:29:35 +0000164 MemTransferInst *TheCopy = nullptr;
Chandler Carruthc908ca12012-08-21 08:39:44 +0000165 if (isOnlyCopiedFromConstantGlobal(AI, TheCopy, ToDelete))
166 return TheCopy;
Craig Topperf40110f2014-04-25 05:29:35 +0000167 return nullptr;
Chandler Carruthc908ca12012-08-21 08:39:44 +0000168}
169
Duncan P. N. Exon Smithc6820ec2015-03-13 19:22:03 +0000170static Instruction *simplifyAllocaArraySize(InstCombiner &IC, AllocaInst &AI) {
Duncan P. N. Exon Smith720762e2015-03-13 19:30:44 +0000171 // Check for array size of 1 (scalar allocation).
Duncan P. N. Exon Smithbe95b4a2015-03-13 19:42:09 +0000172 if (!AI.isArrayAllocation()) {
173 // i32 1 is the canonical array size for scalar allocations.
174 if (AI.getArraySize()->getType()->isIntegerTy(32))
175 return nullptr;
176
177 // Canonicalize it.
178 Value *V = IC.Builder->getInt32(1);
179 AI.setOperand(0, V);
180 return &AI;
181 }
Duncan P. N. Exon Smith720762e2015-03-13 19:30:44 +0000182
Chris Lattnera65e2f72010-01-05 05:57:49 +0000183 // Convert: alloca Ty, C - where C is a constant != 1 into: alloca [C x Ty], 1
Duncan P. N. Exon Smithbb730132015-03-13 19:26:33 +0000184 if (const ConstantInt *C = dyn_cast<ConstantInt>(AI.getArraySize())) {
185 Type *NewTy = ArrayType::get(AI.getAllocatedType(), C->getZExtValue());
186 AllocaInst *New = IC.Builder->CreateAlloca(NewTy, nullptr, AI.getName());
187 New->setAlignment(AI.getAlignment());
Chris Lattnera65e2f72010-01-05 05:57:49 +0000188
Duncan P. N. Exon Smithbb730132015-03-13 19:26:33 +0000189 // Scan to the end of the allocation instructions, to skip over a block of
190 // allocas if possible...also skip interleaved debug info
191 //
Duncan P. N. Exon Smith9f8aaf22015-10-13 16:59:33 +0000192 BasicBlock::iterator It(New);
Duncan P. N. Exon Smithbb730132015-03-13 19:26:33 +0000193 while (isa<AllocaInst>(*It) || isa<DbgInfoIntrinsic>(*It))
194 ++It;
Chris Lattnera65e2f72010-01-05 05:57:49 +0000195
Duncan P. N. Exon Smithbb730132015-03-13 19:26:33 +0000196 // Now that I is pointing to the first non-allocation-inst in the block,
197 // insert our getelementptr instruction...
198 //
199 Type *IdxTy = IC.getDataLayout().getIntPtrType(AI.getType());
200 Value *NullIdx = Constant::getNullValue(IdxTy);
201 Value *Idx[2] = {NullIdx, NullIdx};
202 Instruction *GEP =
Matt Arsenault640ff9d2013-08-14 00:24:05 +0000203 GetElementPtrInst::CreateInBounds(New, Idx, New->getName() + ".sub");
Duncan P. N. Exon Smithbb730132015-03-13 19:26:33 +0000204 IC.InsertNewInstBefore(GEP, *It);
Chris Lattnera65e2f72010-01-05 05:57:49 +0000205
Duncan P. N. Exon Smithbb730132015-03-13 19:26:33 +0000206 // Now make everything use the getelementptr instead of the original
207 // allocation.
Sanjay Patel4b198802016-02-01 22:23:39 +0000208 return IC.replaceInstUsesWith(AI, GEP);
Chris Lattnera65e2f72010-01-05 05:57:49 +0000209 }
210
Duncan P. N. Exon Smithbb730132015-03-13 19:26:33 +0000211 if (isa<UndefValue>(AI.getArraySize()))
Sanjay Patel4b198802016-02-01 22:23:39 +0000212 return IC.replaceInstUsesWith(AI, Constant::getNullValue(AI.getType()));
Duncan P. N. Exon Smithbb730132015-03-13 19:26:33 +0000213
Duncan P. N. Exon Smith07ff9b02015-03-13 19:34:55 +0000214 // Ensure that the alloca array size argument has type intptr_t, so that
215 // any casting is exposed early.
216 Type *IntPtrTy = IC.getDataLayout().getIntPtrType(AI.getType());
217 if (AI.getArraySize()->getType() != IntPtrTy) {
218 Value *V = IC.Builder->CreateIntCast(AI.getArraySize(), IntPtrTy, false);
219 AI.setOperand(0, V);
220 return &AI;
221 }
222
Duncan P. N. Exon Smithc6820ec2015-03-13 19:22:03 +0000223 return nullptr;
224}
225
226Instruction *InstCombiner::visitAllocaInst(AllocaInst &AI) {
227 if (auto *I = simplifyAllocaArraySize(*this, AI))
228 return I;
229
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000230 if (AI.getAllocatedType()->isSized()) {
Chris Lattnera65e2f72010-01-05 05:57:49 +0000231 // If the alignment is 0 (unspecified), assign it the preferred alignment.
232 if (AI.getAlignment() == 0)
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000233 AI.setAlignment(DL.getPrefTypeAlignment(AI.getAllocatedType()));
Duncan Sands8bc764a2012-06-26 13:39:21 +0000234
235 // Move all alloca's of zero byte objects to the entry block and merge them
236 // together. Note that we only do this for alloca's, because malloc should
237 // allocate and return a unique pointer, even for a zero byte allocation.
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000238 if (DL.getTypeAllocSize(AI.getAllocatedType()) == 0) {
Duncan Sands8bc764a2012-06-26 13:39:21 +0000239 // For a zero sized alloca there is no point in doing an array allocation.
240 // This is helpful if the array size is a complicated expression not used
241 // elsewhere.
242 if (AI.isArrayAllocation()) {
243 AI.setOperand(0, ConstantInt::get(AI.getArraySize()->getType(), 1));
244 return &AI;
245 }
246
247 // Get the first instruction in the entry block.
248 BasicBlock &EntryBlock = AI.getParent()->getParent()->getEntryBlock();
249 Instruction *FirstInst = EntryBlock.getFirstNonPHIOrDbg();
250 if (FirstInst != &AI) {
251 // If the entry block doesn't start with a zero-size alloca then move
252 // this one to the start of the entry block. There is no problem with
253 // dominance as the array size was forced to a constant earlier already.
254 AllocaInst *EntryAI = dyn_cast<AllocaInst>(FirstInst);
255 if (!EntryAI || !EntryAI->getAllocatedType()->isSized() ||
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000256 DL.getTypeAllocSize(EntryAI->getAllocatedType()) != 0) {
Duncan Sands8bc764a2012-06-26 13:39:21 +0000257 AI.moveBefore(FirstInst);
258 return &AI;
259 }
260
Richard Osborneb68053e2012-09-18 09:31:44 +0000261 // If the alignment of the entry block alloca is 0 (unspecified),
262 // assign it the preferred alignment.
263 if (EntryAI->getAlignment() == 0)
264 EntryAI->setAlignment(
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000265 DL.getPrefTypeAlignment(EntryAI->getAllocatedType()));
Duncan Sands8bc764a2012-06-26 13:39:21 +0000266 // Replace this zero-sized alloca with the one at the start of the entry
267 // block after ensuring that the address will be aligned enough for both
268 // types.
Richard Osborneb68053e2012-09-18 09:31:44 +0000269 unsigned MaxAlign = std::max(EntryAI->getAlignment(),
270 AI.getAlignment());
Duncan Sands8bc764a2012-06-26 13:39:21 +0000271 EntryAI->setAlignment(MaxAlign);
272 if (AI.getType() != EntryAI->getType())
273 return new BitCastInst(EntryAI, AI.getType());
Sanjay Patel4b198802016-02-01 22:23:39 +0000274 return replaceInstUsesWith(AI, EntryAI);
Duncan Sands8bc764a2012-06-26 13:39:21 +0000275 }
276 }
Chris Lattnera65e2f72010-01-05 05:57:49 +0000277 }
278
Eli Friedmanb14873c2012-11-26 23:04:53 +0000279 if (AI.getAlignment()) {
Richard Osborne2fd29bf2012-09-24 17:10:03 +0000280 // Check to see if this allocation is only modified by a memcpy/memmove from
281 // a constant global whose alignment is equal to or exceeds that of the
282 // allocation. If this is the case, we can change all users to use
283 // the constant global instead. This is commonly produced by the CFE by
284 // constructs like "void foo() { int A[] = {1,2,3,4,5,6,7,8,9...}; }" if 'A'
285 // is only subsequently read.
286 SmallVector<Instruction *, 4> ToDelete;
287 if (MemTransferInst *Copy = isOnlyCopiedFromConstantGlobal(&AI, ToDelete)) {
Chandler Carruth66b31302015-01-04 12:03:27 +0000288 unsigned SourceAlign = getOrEnforceKnownAlignment(
Justin Bogner99798402016-08-05 01:06:44 +0000289 Copy->getSource(), AI.getAlignment(), DL, &AI, &AC, &DT);
Eli Friedmanb14873c2012-11-26 23:04:53 +0000290 if (AI.getAlignment() <= SourceAlign) {
Richard Osborne2fd29bf2012-09-24 17:10:03 +0000291 DEBUG(dbgs() << "Found alloca equal to global: " << AI << '\n');
292 DEBUG(dbgs() << " memcpy = " << *Copy << '\n');
293 for (unsigned i = 0, e = ToDelete.size(); i != e; ++i)
Sanjay Patel4b198802016-02-01 22:23:39 +0000294 eraseInstFromFunction(*ToDelete[i]);
Richard Osborne2fd29bf2012-09-24 17:10:03 +0000295 Constant *TheSrc = cast<Constant>(Copy->getSource());
Matt Arsenaultbbf18c62013-12-07 02:58:45 +0000296 Constant *Cast
297 = ConstantExpr::getPointerBitCastOrAddrSpaceCast(TheSrc, AI.getType());
Sanjay Patel4b198802016-02-01 22:23:39 +0000298 Instruction *NewI = replaceInstUsesWith(AI, Cast);
299 eraseInstFromFunction(*Copy);
Richard Osborne2fd29bf2012-09-24 17:10:03 +0000300 ++NumGlobalCopies;
301 return NewI;
302 }
Chandler Carruthc908ca12012-08-21 08:39:44 +0000303 }
304 }
305
Nuno Lopes95cc4f32012-07-09 18:38:20 +0000306 // At last, use the generic allocation site handler to aggressively remove
307 // unused allocas.
308 return visitAllocSite(AI);
Chris Lattnera65e2f72010-01-05 05:57:49 +0000309}
310
Chandler Carruthbc6378d2014-10-19 10:46:46 +0000311/// \brief Helper to combine a load to a new type.
312///
313/// This just does the work of combining a load to a new type. It handles
314/// metadata, etc., and returns the new instruction. The \c NewTy should be the
315/// loaded *value* type. This will convert it to a pointer, cast the operand to
316/// that pointer type, load it, etc.
317///
318/// Note that this will create all of the instructions with whatever insert
319/// point the \c InstCombiner currently is using.
Mehdi Amini2668a482015-05-07 05:52:40 +0000320static LoadInst *combineLoadToNewType(InstCombiner &IC, LoadInst &LI, Type *NewTy,
321 const Twine &Suffix = "") {
Chandler Carruthbc6378d2014-10-19 10:46:46 +0000322 Value *Ptr = LI.getPointerOperand();
323 unsigned AS = LI.getPointerAddressSpace();
Duncan P. N. Exon Smithde36e802014-11-11 21:30:22 +0000324 SmallVector<std::pair<unsigned, MDNode *>, 8> MD;
Chandler Carruthbc6378d2014-10-19 10:46:46 +0000325 LI.getAllMetadata(MD);
326
327 LoadInst *NewLoad = IC.Builder->CreateAlignedLoad(
328 IC.Builder->CreateBitCast(Ptr, NewTy->getPointerTo(AS)),
Philip Reames6f4d0082016-05-06 22:17:01 +0000329 LI.getAlignment(), LI.isVolatile(), LI.getName() + Suffix);
330 NewLoad->setAtomic(LI.getOrdering(), LI.getSynchScope());
Charles Davis33d1dc02015-02-25 05:10:25 +0000331 MDBuilder MDB(NewLoad->getContext());
Chandler Carruthbc6378d2014-10-19 10:46:46 +0000332 for (const auto &MDPair : MD) {
333 unsigned ID = MDPair.first;
Duncan P. N. Exon Smithde36e802014-11-11 21:30:22 +0000334 MDNode *N = MDPair.second;
Chandler Carruthbc6378d2014-10-19 10:46:46 +0000335 // Note, essentially every kind of metadata should be preserved here! This
336 // routine is supposed to clone a load instruction changing *only its type*.
337 // The only metadata it makes sense to drop is metadata which is invalidated
338 // when the pointer type changes. This should essentially never be the case
339 // in LLVM, but we explicitly switch over only known metadata to be
340 // conservatively correct. If you are adding metadata to LLVM which pertains
341 // to loads, you almost certainly want to add it here.
342 switch (ID) {
343 case LLVMContext::MD_dbg:
344 case LLVMContext::MD_tbaa:
345 case LLVMContext::MD_prof:
346 case LLVMContext::MD_fpmath:
347 case LLVMContext::MD_tbaa_struct:
348 case LLVMContext::MD_invariant_load:
349 case LLVMContext::MD_alias_scope:
350 case LLVMContext::MD_noalias:
Philip Reames5a3f5f72014-10-21 00:13:20 +0000351 case LLVMContext::MD_nontemporal:
352 case LLVMContext::MD_mem_parallel_loop_access:
Chandler Carruthbc6378d2014-10-19 10:46:46 +0000353 // All of these directly apply.
354 NewLoad->setMetadata(ID, N);
355 break;
356
Chandler Carruth87fdafc2015-02-13 02:30:01 +0000357 case LLVMContext::MD_nonnull:
Charles Davis33d1dc02015-02-25 05:10:25 +0000358 // This only directly applies if the new type is also a pointer.
359 if (NewTy->isPointerTy()) {
Chandler Carruth87fdafc2015-02-13 02:30:01 +0000360 NewLoad->setMetadata(ID, N);
Charles Davis33d1dc02015-02-25 05:10:25 +0000361 break;
362 }
363 // If it's integral now, translate it to !range metadata.
364 if (NewTy->isIntegerTy()) {
365 auto *ITy = cast<IntegerType>(NewTy);
366 auto *NullInt = ConstantExpr::getPtrToInt(
367 ConstantPointerNull::get(cast<PointerType>(Ptr->getType())), ITy);
368 auto *NonNullInt =
369 ConstantExpr::getAdd(NullInt, ConstantInt::get(ITy, 1));
370 NewLoad->setMetadata(LLVMContext::MD_range,
371 MDB.createRange(NonNullInt, NullInt));
372 }
Chandler Carruth87fdafc2015-02-13 02:30:01 +0000373 break;
Artur Pilipenko5c5011d2015-11-02 17:53:51 +0000374 case LLVMContext::MD_align:
375 case LLVMContext::MD_dereferenceable:
376 case LLVMContext::MD_dereferenceable_or_null:
377 // These only directly apply if the new type is also a pointer.
378 if (NewTy->isPointerTy())
379 NewLoad->setMetadata(ID, N);
380 break;
Chandler Carruthbc6378d2014-10-19 10:46:46 +0000381 case LLVMContext::MD_range:
382 // FIXME: It would be nice to propagate this in some way, but the type
David Majnemer80dca0c2016-10-11 01:00:45 +0000383 // conversions make it hard.
384
385 // If it's a pointer now and the range does not contain 0, make it !nonnull.
386 if (NewTy->isPointerTy()) {
387 unsigned BitWidth = IC.getDataLayout().getTypeSizeInBits(NewTy);
388 if (!getConstantRangeFromMetadata(*N).contains(APInt(BitWidth, 0))) {
389 MDNode *NN = MDNode::get(LI.getContext(), None);
390 NewLoad->setMetadata(LLVMContext::MD_nonnull, NN);
391 }
392 }
Chandler Carruthbc6378d2014-10-19 10:46:46 +0000393 break;
394 }
395 }
Chandler Carruthbc6378d2014-10-19 10:46:46 +0000396 return NewLoad;
397}
398
Chandler Carruthfa11d832015-01-22 03:34:54 +0000399/// \brief Combine a store to a new type.
400///
401/// Returns the newly created store instruction.
402static StoreInst *combineStoreToNewValue(InstCombiner &IC, StoreInst &SI, Value *V) {
403 Value *Ptr = SI.getPointerOperand();
404 unsigned AS = SI.getPointerAddressSpace();
405 SmallVector<std::pair<unsigned, MDNode *>, 8> MD;
406 SI.getAllMetadata(MD);
407
408 StoreInst *NewStore = IC.Builder->CreateAlignedStore(
409 V, IC.Builder->CreateBitCast(Ptr, V->getType()->getPointerTo(AS)),
Philip Reames6f4d0082016-05-06 22:17:01 +0000410 SI.getAlignment(), SI.isVolatile());
411 NewStore->setAtomic(SI.getOrdering(), SI.getSynchScope());
Chandler Carruthfa11d832015-01-22 03:34:54 +0000412 for (const auto &MDPair : MD) {
413 unsigned ID = MDPair.first;
414 MDNode *N = MDPair.second;
415 // Note, essentially every kind of metadata should be preserved here! This
416 // routine is supposed to clone a store instruction changing *only its
417 // type*. The only metadata it makes sense to drop is metadata which is
418 // invalidated when the pointer type changes. This should essentially
419 // never be the case in LLVM, but we explicitly switch over only known
420 // metadata to be conservatively correct. If you are adding metadata to
421 // LLVM which pertains to stores, you almost certainly want to add it
422 // here.
423 switch (ID) {
424 case LLVMContext::MD_dbg:
425 case LLVMContext::MD_tbaa:
426 case LLVMContext::MD_prof:
427 case LLVMContext::MD_fpmath:
428 case LLVMContext::MD_tbaa_struct:
429 case LLVMContext::MD_alias_scope:
430 case LLVMContext::MD_noalias:
431 case LLVMContext::MD_nontemporal:
432 case LLVMContext::MD_mem_parallel_loop_access:
Chandler Carruthfa11d832015-01-22 03:34:54 +0000433 // All of these directly apply.
434 NewStore->setMetadata(ID, N);
435 break;
436
437 case LLVMContext::MD_invariant_load:
Chandler Carruth87fdafc2015-02-13 02:30:01 +0000438 case LLVMContext::MD_nonnull:
Chandler Carruthfa11d832015-01-22 03:34:54 +0000439 case LLVMContext::MD_range:
Artur Pilipenko5c5011d2015-11-02 17:53:51 +0000440 case LLVMContext::MD_align:
441 case LLVMContext::MD_dereferenceable:
442 case LLVMContext::MD_dereferenceable_or_null:
Chandler Carruth87fdafc2015-02-13 02:30:01 +0000443 // These don't apply for stores.
Chandler Carruthfa11d832015-01-22 03:34:54 +0000444 break;
445 }
446 }
447
448 return NewStore;
449}
450
JF Bastien3e2e69f2016-04-21 19:41:48 +0000451/// \brief Combine loads to match the type of their uses' value after looking
Chandler Carruth2f75fcf2014-10-18 06:36:22 +0000452/// through intervening bitcasts.
453///
454/// The core idea here is that if the result of a load is used in an operation,
455/// we should load the type most conducive to that operation. For example, when
456/// loading an integer and converting that immediately to a pointer, we should
457/// instead directly load a pointer.
458///
459/// However, this routine must never change the width of a load or the number of
460/// loads as that would introduce a semantic change. This combine is expected to
461/// be a semantic no-op which just allows loads to more closely model the types
462/// of their consuming operations.
463///
464/// Currently, we also refuse to change the precise type used for an atomic load
465/// or a volatile load. This is debatable, and might be reasonable to change
466/// later. However, it is risky in case some backend or other part of LLVM is
467/// relying on the exact type loaded to select appropriate atomic operations.
468static Instruction *combineLoadToOperationType(InstCombiner &IC, LoadInst &LI) {
Philip Reames6f4d0082016-05-06 22:17:01 +0000469 // FIXME: We could probably with some care handle both volatile and ordered
470 // atomic loads here but it isn't clear that this is important.
471 if (!LI.isUnordered())
Chandler Carruth2f75fcf2014-10-18 06:36:22 +0000472 return nullptr;
Chris Lattnera65e2f72010-01-05 05:57:49 +0000473
Chandler Carruth2f75fcf2014-10-18 06:36:22 +0000474 if (LI.use_empty())
475 return nullptr;
Chris Lattnera65e2f72010-01-05 05:57:49 +0000476
Arnold Schwaighofer5d335552016-09-10 18:14:57 +0000477 // swifterror values can't be bitcasted.
478 if (LI.getPointerOperand()->isSwiftError())
479 return nullptr;
480
Chandler Carruthcd8522e2015-01-22 05:08:12 +0000481 Type *Ty = LI.getType();
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000482 const DataLayout &DL = IC.getDataLayout();
Chandler Carruthcd8522e2015-01-22 05:08:12 +0000483
484 // Try to canonicalize loads which are only ever stored to operate over
485 // integers instead of any other type. We only do this when the loaded type
486 // is sized and has a size exactly the same as its store size and the store
487 // size is a legal integer type.
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000488 if (!Ty->isIntegerTy() && Ty->isSized() &&
489 DL.isLegalInteger(DL.getTypeStoreSizeInBits(Ty)) &&
Sanjoy Dasba04d3a2016-08-06 02:58:48 +0000490 DL.getTypeStoreSizeInBits(Ty) == DL.getTypeSizeInBits(Ty) &&
491 !DL.isNonIntegralPointerType(Ty)) {
David Majnemer0a16c222016-08-11 21:15:00 +0000492 if (all_of(LI.users(), [&LI](User *U) {
Chandler Carruthcd8522e2015-01-22 05:08:12 +0000493 auto *SI = dyn_cast<StoreInst>(U);
494 return SI && SI->getPointerOperand() != &LI;
495 })) {
496 LoadInst *NewLoad = combineLoadToNewType(
497 IC, LI,
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000498 Type::getIntNTy(LI.getContext(), DL.getTypeStoreSizeInBits(Ty)));
Chandler Carruthcd8522e2015-01-22 05:08:12 +0000499 // Replace all the stores with stores of the newly loaded value.
500 for (auto UI = LI.user_begin(), UE = LI.user_end(); UI != UE;) {
501 auto *SI = cast<StoreInst>(*UI++);
502 IC.Builder->SetInsertPoint(SI);
503 combineStoreToNewValue(IC, *SI, NewLoad);
Sanjay Patel4b198802016-02-01 22:23:39 +0000504 IC.eraseInstFromFunction(*SI);
Chandler Carruthcd8522e2015-01-22 05:08:12 +0000505 }
506 assert(LI.use_empty() && "Failed to remove all users of the load!");
507 // Return the old load so the combiner can delete it safely.
508 return &LI;
509 }
510 }
Chris Lattnera65e2f72010-01-05 05:57:49 +0000511
Chandler Carruth2f75fcf2014-10-18 06:36:22 +0000512 // Fold away bit casts of the loaded value by loading the desired type.
Quentin Colombet490cfbe2016-02-11 22:30:41 +0000513 // We can do this for BitCastInsts as well as casts from and to pointer types,
514 // as long as those are noops (i.e., the source or dest type have the same
515 // bitwidth as the target's pointers).
Chandler Carruth2f75fcf2014-10-18 06:36:22 +0000516 if (LI.hasOneUse())
Quentin Colombet490cfbe2016-02-11 22:30:41 +0000517 if (auto* CI = dyn_cast<CastInst>(LI.user_back())) {
518 if (CI->isNoopCast(DL)) {
519 LoadInst *NewLoad = combineLoadToNewType(IC, LI, CI->getDestTy());
520 CI->replaceAllUsesWith(NewLoad);
521 IC.eraseInstFromFunction(*CI);
522 return &LI;
523 }
Chris Lattnera65e2f72010-01-05 05:57:49 +0000524 }
Chandler Carruth2f75fcf2014-10-18 06:36:22 +0000525
Chandler Carrutha7f247e2014-12-09 19:21:16 +0000526 // FIXME: We should also canonicalize loads of vectors when their elements are
527 // cast to other types.
Craig Topperf40110f2014-04-25 05:29:35 +0000528 return nullptr;
Chris Lattnera65e2f72010-01-05 05:57:49 +0000529}
530
Mehdi Amini2668a482015-05-07 05:52:40 +0000531static Instruction *unpackLoadToAggregate(InstCombiner &IC, LoadInst &LI) {
532 // FIXME: We could probably with some care handle both volatile and atomic
533 // stores here but it isn't clear that this is important.
534 if (!LI.isSimple())
535 return nullptr;
536
537 Type *T = LI.getType();
538 if (!T->isAggregateType())
539 return nullptr;
540
Benjamin Kramerc1263532016-03-11 10:20:56 +0000541 StringRef Name = LI.getName();
Bruce Mitchenere9ffb452015-09-12 01:17:08 +0000542 assert(LI.getAlignment() && "Alignment must be set at this point");
Mehdi Amini2668a482015-05-07 05:52:40 +0000543
544 if (auto *ST = dyn_cast<StructType>(T)) {
545 // If the struct only have one element, we unpack.
Amaury Sechet61a7d622016-02-17 19:21:28 +0000546 auto NumElements = ST->getNumElements();
547 if (NumElements == 1) {
Mehdi Amini2668a482015-05-07 05:52:40 +0000548 LoadInst *NewLoad = combineLoadToNewType(IC, LI, ST->getTypeAtIndex(0U),
549 ".unpack");
Sanjay Patel4b198802016-02-01 22:23:39 +0000550 return IC.replaceInstUsesWith(LI, IC.Builder->CreateInsertValue(
Amaury Sechet61a7d622016-02-17 19:21:28 +0000551 UndefValue::get(T), NewLoad, 0, Name));
Mehdi Amini2668a482015-05-07 05:52:40 +0000552 }
Mehdi Amini1c131b32015-12-15 01:44:07 +0000553
554 // We don't want to break loads with padding here as we'd loose
555 // the knowledge that padding exists for the rest of the pipeline.
556 const DataLayout &DL = IC.getDataLayout();
557 auto *SL = DL.getStructLayout(ST);
558 if (SL->hasPadding())
559 return nullptr;
560
Amaury Sechet61a7d622016-02-17 19:21:28 +0000561 auto Align = LI.getAlignment();
562 if (!Align)
563 Align = DL.getABITypeAlignment(ST);
564
Mehdi Amini1c131b32015-12-15 01:44:07 +0000565 auto *Addr = LI.getPointerOperand();
Amaury Sechet61a7d622016-02-17 19:21:28 +0000566 auto *IdxType = Type::getInt32Ty(T->getContext());
Mehdi Amini1c131b32015-12-15 01:44:07 +0000567 auto *Zero = ConstantInt::get(IdxType, 0);
Amaury Sechet61a7d622016-02-17 19:21:28 +0000568
569 Value *V = UndefValue::get(T);
570 for (unsigned i = 0; i < NumElements; i++) {
Mehdi Amini1c131b32015-12-15 01:44:07 +0000571 Value *Indices[2] = {
572 Zero,
573 ConstantInt::get(IdxType, i),
574 };
Amaury Sechetda71cb72016-02-17 21:21:29 +0000575 auto *Ptr = IC.Builder->CreateInBoundsGEP(ST, Addr, makeArrayRef(Indices),
Benjamin Kramerc1263532016-03-11 10:20:56 +0000576 Name + ".elt");
Amaury Sechet61a7d622016-02-17 19:21:28 +0000577 auto EltAlign = MinAlign(Align, SL->getElementOffset(i));
Benjamin Kramerc1263532016-03-11 10:20:56 +0000578 auto *L = IC.Builder->CreateAlignedLoad(Ptr, EltAlign, Name + ".unpack");
Mehdi Amini1c131b32015-12-15 01:44:07 +0000579 V = IC.Builder->CreateInsertValue(V, L, i);
580 }
581
582 V->setName(Name);
Sanjay Patel4b198802016-02-01 22:23:39 +0000583 return IC.replaceInstUsesWith(LI, V);
Mehdi Amini2668a482015-05-07 05:52:40 +0000584 }
585
David Majnemer58fb0382015-05-11 05:04:22 +0000586 if (auto *AT = dyn_cast<ArrayType>(T)) {
Amaury Sechet7cd3fe72016-03-02 21:28:30 +0000587 auto *ET = AT->getElementType();
588 auto NumElements = AT->getNumElements();
589 if (NumElements == 1) {
590 LoadInst *NewLoad = combineLoadToNewType(IC, LI, ET, ".unpack");
Sanjay Patel4b198802016-02-01 22:23:39 +0000591 return IC.replaceInstUsesWith(LI, IC.Builder->CreateInsertValue(
Amaury Sechet7cd3fe72016-03-02 21:28:30 +0000592 UndefValue::get(T), NewLoad, 0, Name));
David Majnemer58fb0382015-05-11 05:04:22 +0000593 }
Amaury Sechet7cd3fe72016-03-02 21:28:30 +0000594
Davide Italianoda114122016-10-07 20:57:42 +0000595 // Bail out if the array is too large. Ideally we would like to optimize
596 // arrays of arbitrary size but this has a terrible impact on compile time.
597 // The threshold here is chosen arbitrarily, maybe needs a little bit of
598 // tuning.
599 if (NumElements > 1024)
600 return nullptr;
601
Amaury Sechet7cd3fe72016-03-02 21:28:30 +0000602 const DataLayout &DL = IC.getDataLayout();
603 auto EltSize = DL.getTypeAllocSize(ET);
604 auto Align = LI.getAlignment();
605 if (!Align)
606 Align = DL.getABITypeAlignment(T);
607
Amaury Sechet7cd3fe72016-03-02 21:28:30 +0000608 auto *Addr = LI.getPointerOperand();
609 auto *IdxType = Type::getInt64Ty(T->getContext());
610 auto *Zero = ConstantInt::get(IdxType, 0);
611
612 Value *V = UndefValue::get(T);
613 uint64_t Offset = 0;
614 for (uint64_t i = 0; i < NumElements; i++) {
615 Value *Indices[2] = {
616 Zero,
617 ConstantInt::get(IdxType, i),
618 };
619 auto *Ptr = IC.Builder->CreateInBoundsGEP(AT, Addr, makeArrayRef(Indices),
Benjamin Kramerc1263532016-03-11 10:20:56 +0000620 Name + ".elt");
Amaury Sechet7cd3fe72016-03-02 21:28:30 +0000621 auto *L = IC.Builder->CreateAlignedLoad(Ptr, MinAlign(Align, Offset),
Benjamin Kramerc1263532016-03-11 10:20:56 +0000622 Name + ".unpack");
Amaury Sechet7cd3fe72016-03-02 21:28:30 +0000623 V = IC.Builder->CreateInsertValue(V, L, i);
624 Offset += EltSize;
625 }
626
627 V->setName(Name);
628 return IC.replaceInstUsesWith(LI, V);
David Majnemer58fb0382015-05-11 05:04:22 +0000629 }
630
Mehdi Amini2668a482015-05-07 05:52:40 +0000631 return nullptr;
632}
633
Hal Finkel847e05f2015-02-20 03:05:53 +0000634// If we can determine that all possible objects pointed to by the provided
635// pointer value are, not only dereferenceable, but also definitively less than
636// or equal to the provided maximum size, then return true. Otherwise, return
637// false (constant global values and allocas fall into this category).
638//
639// FIXME: This should probably live in ValueTracking (or similar).
640static bool isObjectSizeLessThanOrEq(Value *V, uint64_t MaxSize,
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000641 const DataLayout &DL) {
Hal Finkel847e05f2015-02-20 03:05:53 +0000642 SmallPtrSet<Value *, 4> Visited;
643 SmallVector<Value *, 4> Worklist(1, V);
644
645 do {
646 Value *P = Worklist.pop_back_val();
647 P = P->stripPointerCasts();
648
649 if (!Visited.insert(P).second)
650 continue;
651
652 if (SelectInst *SI = dyn_cast<SelectInst>(P)) {
653 Worklist.push_back(SI->getTrueValue());
654 Worklist.push_back(SI->getFalseValue());
655 continue;
656 }
657
658 if (PHINode *PN = dyn_cast<PHINode>(P)) {
Pete Cooper833f34d2015-05-12 20:05:31 +0000659 for (Value *IncValue : PN->incoming_values())
660 Worklist.push_back(IncValue);
Hal Finkel847e05f2015-02-20 03:05:53 +0000661 continue;
662 }
663
664 if (GlobalAlias *GA = dyn_cast<GlobalAlias>(P)) {
Sanjoy Das99042472016-04-17 04:30:43 +0000665 if (GA->isInterposable())
Hal Finkel847e05f2015-02-20 03:05:53 +0000666 return false;
667 Worklist.push_back(GA->getAliasee());
668 continue;
669 }
670
671 // If we know how big this object is, and it is less than MaxSize, continue
672 // searching. Otherwise, return false.
673 if (AllocaInst *AI = dyn_cast<AllocaInst>(P)) {
674 if (!AI->getAllocatedType()->isSized())
675 return false;
676
677 ConstantInt *CS = dyn_cast<ConstantInt>(AI->getArraySize());
678 if (!CS)
679 return false;
680
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000681 uint64_t TypeSize = DL.getTypeAllocSize(AI->getAllocatedType());
Hal Finkel847e05f2015-02-20 03:05:53 +0000682 // Make sure that, even if the multiplication below would wrap as an
683 // uint64_t, we still do the right thing.
684 if ((CS->getValue().zextOrSelf(128)*APInt(128, TypeSize)).ugt(MaxSize))
685 return false;
686 continue;
687 }
688
689 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(P)) {
690 if (!GV->hasDefinitiveInitializer() || !GV->isConstant())
691 return false;
692
Manuel Jacob5f6eaac2016-01-16 20:30:46 +0000693 uint64_t InitSize = DL.getTypeAllocSize(GV->getValueType());
Hal Finkel847e05f2015-02-20 03:05:53 +0000694 if (InitSize > MaxSize)
695 return false;
696 continue;
697 }
698
699 return false;
700 } while (!Worklist.empty());
701
702 return true;
703}
704
705// If we're indexing into an object of a known size, and the outer index is
706// not a constant, but having any value but zero would lead to undefined
707// behavior, replace it with zero.
708//
709// For example, if we have:
710// @f.a = private unnamed_addr constant [1 x i32] [i32 12], align 4
711// ...
712// %arrayidx = getelementptr inbounds [1 x i32]* @f.a, i64 0, i64 %x
713// ... = load i32* %arrayidx, align 4
714// Then we know that we can replace %x in the GEP with i64 0.
715//
716// FIXME: We could fold any GEP index to zero that would cause UB if it were
717// not zero. Currently, we only handle the first such index. Also, we could
718// also search through non-zero constant indices if we kept track of the
719// offsets those indices implied.
720static bool canReplaceGEPIdxWithZero(InstCombiner &IC, GetElementPtrInst *GEPI,
721 Instruction *MemI, unsigned &Idx) {
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000722 if (GEPI->getNumOperands() < 2)
Hal Finkel847e05f2015-02-20 03:05:53 +0000723 return false;
724
725 // Find the first non-zero index of a GEP. If all indices are zero, return
726 // one past the last index.
727 auto FirstNZIdx = [](const GetElementPtrInst *GEPI) {
728 unsigned I = 1;
729 for (unsigned IE = GEPI->getNumOperands(); I != IE; ++I) {
730 Value *V = GEPI->getOperand(I);
731 if (const ConstantInt *CI = dyn_cast<ConstantInt>(V))
732 if (CI->isZero())
733 continue;
734
735 break;
736 }
737
738 return I;
739 };
740
741 // Skip through initial 'zero' indices, and find the corresponding pointer
742 // type. See if the next index is not a constant.
743 Idx = FirstNZIdx(GEPI);
744 if (Idx == GEPI->getNumOperands())
745 return false;
746 if (isa<Constant>(GEPI->getOperand(Idx)))
747 return false;
748
749 SmallVector<Value *, 4> Ops(GEPI->idx_begin(), GEPI->idx_begin() + Idx);
Eduard Burtescu19eb0312016-01-19 17:28:00 +0000750 Type *AllocTy =
751 GetElementPtrInst::getIndexedType(GEPI->getSourceElementType(), Ops);
Hal Finkel847e05f2015-02-20 03:05:53 +0000752 if (!AllocTy || !AllocTy->isSized())
753 return false;
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000754 const DataLayout &DL = IC.getDataLayout();
755 uint64_t TyAllocSize = DL.getTypeAllocSize(AllocTy);
Hal Finkel847e05f2015-02-20 03:05:53 +0000756
757 // If there are more indices after the one we might replace with a zero, make
758 // sure they're all non-negative. If any of them are negative, the overall
759 // address being computed might be before the base address determined by the
760 // first non-zero index.
761 auto IsAllNonNegative = [&]() {
762 for (unsigned i = Idx+1, e = GEPI->getNumOperands(); i != e; ++i) {
763 bool KnownNonNegative, KnownNegative;
764 IC.ComputeSignBit(GEPI->getOperand(i), KnownNonNegative,
765 KnownNegative, 0, MemI);
766 if (KnownNonNegative)
767 continue;
768 return false;
769 }
770
771 return true;
772 };
773
774 // FIXME: If the GEP is not inbounds, and there are extra indices after the
775 // one we'll replace, those could cause the address computation to wrap
776 // (rendering the IsAllNonNegative() check below insufficient). We can do
Bruce Mitchenere9ffb452015-09-12 01:17:08 +0000777 // better, ignoring zero indices (and other indices we can prove small
Hal Finkel847e05f2015-02-20 03:05:53 +0000778 // enough not to wrap).
779 if (Idx+1 != GEPI->getNumOperands() && !GEPI->isInBounds())
780 return false;
781
782 // Note that isObjectSizeLessThanOrEq will return true only if the pointer is
783 // also known to be dereferenceable.
784 return isObjectSizeLessThanOrEq(GEPI->getOperand(0), TyAllocSize, DL) &&
785 IsAllNonNegative();
786}
787
788// If we're indexing into an object with a variable index for the memory
789// access, but the object has only one element, we can assume that the index
790// will always be zero. If we replace the GEP, return it.
791template <typename T>
792static Instruction *replaceGEPIdxWithZero(InstCombiner &IC, Value *Ptr,
793 T &MemI) {
794 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(Ptr)) {
795 unsigned Idx;
796 if (canReplaceGEPIdxWithZero(IC, GEPI, &MemI, Idx)) {
797 Instruction *NewGEPI = GEPI->clone();
798 NewGEPI->setOperand(Idx,
799 ConstantInt::get(GEPI->getOperand(Idx)->getType(), 0));
800 NewGEPI->insertBefore(GEPI);
801 MemI.setOperand(MemI.getPointerOperandIndex(), NewGEPI);
802 return NewGEPI;
803 }
804 }
805
806 return nullptr;
807}
808
Chris Lattnera65e2f72010-01-05 05:57:49 +0000809Instruction *InstCombiner::visitLoadInst(LoadInst &LI) {
810 Value *Op = LI.getOperand(0);
811
Chandler Carruth2f75fcf2014-10-18 06:36:22 +0000812 // Try to canonicalize the loaded type.
813 if (Instruction *Res = combineLoadToOperationType(*this, LI))
814 return Res;
815
Chris Lattnera65e2f72010-01-05 05:57:49 +0000816 // Attempt to improve the alignment.
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000817 unsigned KnownAlign = getOrEnforceKnownAlignment(
Justin Bogner99798402016-08-05 01:06:44 +0000818 Op, DL.getPrefTypeAlignment(LI.getType()), DL, &LI, &AC, &DT);
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000819 unsigned LoadAlign = LI.getAlignment();
820 unsigned EffectiveLoadAlign =
821 LoadAlign != 0 ? LoadAlign : DL.getABITypeAlignment(LI.getType());
Dan Gohman36196602010-08-03 18:20:32 +0000822
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000823 if (KnownAlign > EffectiveLoadAlign)
824 LI.setAlignment(KnownAlign);
825 else if (LoadAlign == 0)
826 LI.setAlignment(EffectiveLoadAlign);
Chris Lattnera65e2f72010-01-05 05:57:49 +0000827
Hal Finkel847e05f2015-02-20 03:05:53 +0000828 // Replace GEP indices if possible.
829 if (Instruction *NewGEPI = replaceGEPIdxWithZero(*this, Op, LI)) {
830 Worklist.Add(NewGEPI);
831 return &LI;
832 }
833
Mehdi Amini2668a482015-05-07 05:52:40 +0000834 if (Instruction *Res = unpackLoadToAggregate(*this, LI))
835 return Res;
836
Chris Lattnera65e2f72010-01-05 05:57:49 +0000837 // Do really simple store-to-load forwarding and load CSE, to catch cases
Duncan Sands75b5d272011-02-15 09:23:02 +0000838 // where there are several consecutive memory accesses to the same location,
Chris Lattnera65e2f72010-01-05 05:57:49 +0000839 // separated by a few arithmetic operations.
Duncan P. N. Exon Smith9f8aaf22015-10-13 16:59:33 +0000840 BasicBlock::iterator BBI(LI);
Eli Friedmanbd254a62016-06-16 02:33:42 +0000841 bool IsLoadCSE = false;
Larisse Voufo532bf712015-09-18 19:14:35 +0000842 if (Value *AvailableVal =
Eduard Burtescue2a69172016-01-22 01:51:51 +0000843 FindAvailableLoadedValue(&LI, LI.getParent(), BBI,
Eli Friedman02419a92016-08-08 04:10:22 +0000844 DefMaxInstsToScan, AA, &IsLoadCSE)) {
Eli Friedmanbd254a62016-06-16 02:33:42 +0000845 if (IsLoadCSE) {
846 LoadInst *NLI = cast<LoadInst>(AvailableVal);
Bjorn Steinbrinka91fd092015-07-10 06:55:44 +0000847 unsigned KnownIDs[] = {
Artur Pilipenko5c5011d2015-11-02 17:53:51 +0000848 LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope,
849 LLVMContext::MD_noalias, LLVMContext::MD_range,
850 LLVMContext::MD_invariant_load, LLVMContext::MD_nonnull,
851 LLVMContext::MD_invariant_group, LLVMContext::MD_align,
852 LLVMContext::MD_dereferenceable,
853 LLVMContext::MD_dereferenceable_or_null};
Bjorn Steinbrinka91fd092015-07-10 06:55:44 +0000854 combineMetadata(NLI, &LI, KnownIDs);
Bjorn Steinbrinka91fd092015-07-10 06:55:44 +0000855 };
856
Sanjay Patel4b198802016-02-01 22:23:39 +0000857 return replaceInstUsesWith(
Chandler Carruth1a3c2c42014-11-25 08:20:27 +0000858 LI, Builder->CreateBitOrPointerCast(AvailableVal, LI.getType(),
859 LI.getName() + ".cast"));
Bjorn Steinbrinka91fd092015-07-10 06:55:44 +0000860 }
Chris Lattnera65e2f72010-01-05 05:57:49 +0000861
Philip Reames3ac07182016-04-21 17:45:05 +0000862 // None of the following transforms are legal for volatile/ordered atomic
863 // loads. Most of them do apply for unordered atomics.
864 if (!LI.isUnordered()) return nullptr;
Philip Reamesac550902016-04-21 17:03:33 +0000865
Chris Lattnera65e2f72010-01-05 05:57:49 +0000866 // load(gep null, ...) -> unreachable
867 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(Op)) {
868 const Value *GEPI0 = GEPI->getOperand(0);
869 // TODO: Consider a target hook for valid address spaces for this xform.
870 if (isa<ConstantPointerNull>(GEPI0) && GEPI->getPointerAddressSpace() == 0){
871 // Insert a new store to null instruction before the load to indicate
872 // that this code is not reachable. We do this instead of inserting
873 // an unreachable instruction directly because we cannot modify the
874 // CFG.
875 new StoreInst(UndefValue::get(LI.getType()),
876 Constant::getNullValue(Op->getType()), &LI);
Sanjay Patel4b198802016-02-01 22:23:39 +0000877 return replaceInstUsesWith(LI, UndefValue::get(LI.getType()));
Chris Lattnera65e2f72010-01-05 05:57:49 +0000878 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000879 }
Chris Lattnera65e2f72010-01-05 05:57:49 +0000880
881 // load null/undef -> unreachable
882 // TODO: Consider a target hook for valid address spaces for this xform.
883 if (isa<UndefValue>(Op) ||
884 (isa<ConstantPointerNull>(Op) && LI.getPointerAddressSpace() == 0)) {
885 // Insert a new store to null instruction before the load to indicate that
886 // this code is not reachable. We do this instead of inserting an
887 // unreachable instruction directly because we cannot modify the CFG.
888 new StoreInst(UndefValue::get(LI.getType()),
889 Constant::getNullValue(Op->getType()), &LI);
Sanjay Patel4b198802016-02-01 22:23:39 +0000890 return replaceInstUsesWith(LI, UndefValue::get(LI.getType()));
Chris Lattnera65e2f72010-01-05 05:57:49 +0000891 }
892
Chris Lattnera65e2f72010-01-05 05:57:49 +0000893 if (Op->hasOneUse()) {
894 // Change select and PHI nodes to select values instead of addresses: this
895 // helps alias analysis out a lot, allows many others simplifications, and
896 // exposes redundancy in the code.
897 //
898 // Note that we cannot do the transformation unless we know that the
899 // introduced loads cannot trap! Something like this is valid as long as
900 // the condition is always false: load (select bool %C, int* null, int* %G),
901 // but it would not be valid if we transformed it to load from null
902 // unconditionally.
903 //
904 if (SelectInst *SI = dyn_cast<SelectInst>(Op)) {
905 // load (select (Cond, &V1, &V2)) --> select(Cond, load &V1, load &V2).
Bob Wilson56600a12010-01-30 04:42:39 +0000906 unsigned Align = LI.getAlignment();
Artur Pilipenko9bb6bea2016-04-27 11:00:48 +0000907 if (isSafeToLoadUnconditionally(SI->getOperand(1), Align, DL, SI) &&
908 isSafeToLoadUnconditionally(SI->getOperand(2), Align, DL, SI)) {
Bob Wilson4b71b6c2010-01-30 00:41:10 +0000909 LoadInst *V1 = Builder->CreateLoad(SI->getOperand(1),
Bob Wilson56600a12010-01-30 04:42:39 +0000910 SI->getOperand(1)->getName()+".val");
Bob Wilson4b71b6c2010-01-30 00:41:10 +0000911 LoadInst *V2 = Builder->CreateLoad(SI->getOperand(2),
Bob Wilson56600a12010-01-30 04:42:39 +0000912 SI->getOperand(2)->getName()+".val");
Philip Reamesa98c7ea2016-04-21 17:59:40 +0000913 assert(LI.isUnordered() && "implied by above");
Bob Wilson56600a12010-01-30 04:42:39 +0000914 V1->setAlignment(Align);
Philip Reamesa98c7ea2016-04-21 17:59:40 +0000915 V1->setAtomic(LI.getOrdering(), LI.getSynchScope());
Bob Wilson56600a12010-01-30 04:42:39 +0000916 V2->setAlignment(Align);
Philip Reamesa98c7ea2016-04-21 17:59:40 +0000917 V2->setAtomic(LI.getOrdering(), LI.getSynchScope());
Chris Lattnera65e2f72010-01-05 05:57:49 +0000918 return SelectInst::Create(SI->getCondition(), V1, V2);
919 }
920
921 // load (select (cond, null, P)) -> load P
Larisse Voufo532bf712015-09-18 19:14:35 +0000922 if (isa<ConstantPointerNull>(SI->getOperand(1)) &&
Philip Reames5ad26c32014-12-29 22:46:21 +0000923 LI.getPointerAddressSpace() == 0) {
924 LI.setOperand(0, SI->getOperand(2));
925 return &LI;
926 }
Chris Lattnera65e2f72010-01-05 05:57:49 +0000927
928 // load (select (cond, P, null)) -> load P
Philip Reames5ad26c32014-12-29 22:46:21 +0000929 if (isa<ConstantPointerNull>(SI->getOperand(2)) &&
930 LI.getPointerAddressSpace() == 0) {
931 LI.setOperand(0, SI->getOperand(1));
932 return &LI;
933 }
Chris Lattnera65e2f72010-01-05 05:57:49 +0000934 }
935 }
Craig Topperf40110f2014-04-25 05:29:35 +0000936 return nullptr;
Chris Lattnera65e2f72010-01-05 05:57:49 +0000937}
938
Arch D. Robisonbe0490a2016-04-25 22:22:39 +0000939/// \brief Look for extractelement/insertvalue sequence that acts like a bitcast.
940///
941/// \returns underlying value that was "cast", or nullptr otherwise.
942///
943/// For example, if we have:
944///
945/// %E0 = extractelement <2 x double> %U, i32 0
946/// %V0 = insertvalue [2 x double] undef, double %E0, 0
947/// %E1 = extractelement <2 x double> %U, i32 1
948/// %V1 = insertvalue [2 x double] %V0, double %E1, 1
949///
950/// and the layout of a <2 x double> is isomorphic to a [2 x double],
951/// then %V1 can be safely approximated by a conceptual "bitcast" of %U.
952/// Note that %U may contain non-undef values where %V1 has undef.
953static Value *likeBitCastFromVector(InstCombiner &IC, Value *V) {
954 Value *U = nullptr;
955 while (auto *IV = dyn_cast<InsertValueInst>(V)) {
956 auto *E = dyn_cast<ExtractElementInst>(IV->getInsertedValueOperand());
957 if (!E)
958 return nullptr;
959 auto *W = E->getVectorOperand();
960 if (!U)
961 U = W;
962 else if (U != W)
963 return nullptr;
964 auto *CI = dyn_cast<ConstantInt>(E->getIndexOperand());
965 if (!CI || IV->getNumIndices() != 1 || CI->getZExtValue() != *IV->idx_begin())
966 return nullptr;
967 V = IV->getAggregateOperand();
968 }
969 if (!isa<UndefValue>(V) ||!U)
970 return nullptr;
971
972 auto *UT = cast<VectorType>(U->getType());
973 auto *VT = V->getType();
974 // Check that types UT and VT are bitwise isomorphic.
975 const auto &DL = IC.getDataLayout();
976 if (DL.getTypeStoreSizeInBits(UT) != DL.getTypeStoreSizeInBits(VT)) {
977 return nullptr;
978 }
979 if (auto *AT = dyn_cast<ArrayType>(VT)) {
980 if (AT->getNumElements() != UT->getNumElements())
981 return nullptr;
982 } else {
983 auto *ST = cast<StructType>(VT);
984 if (ST->getNumElements() != UT->getNumElements())
985 return nullptr;
986 for (const auto *EltT : ST->elements()) {
987 if (EltT != UT->getElementType())
988 return nullptr;
989 }
990 }
991 return U;
992}
993
Chandler Carruth816d26f2014-11-25 10:09:51 +0000994/// \brief Combine stores to match the type of value being stored.
995///
996/// The core idea here is that the memory does not have any intrinsic type and
997/// where we can we should match the type of a store to the type of value being
998/// stored.
999///
1000/// However, this routine must never change the width of a store or the number of
1001/// stores as that would introduce a semantic change. This combine is expected to
1002/// be a semantic no-op which just allows stores to more closely model the types
1003/// of their incoming values.
1004///
1005/// Currently, we also refuse to change the precise type used for an atomic or
1006/// volatile store. This is debatable, and might be reasonable to change later.
1007/// However, it is risky in case some backend or other part of LLVM is relying
1008/// on the exact type stored to select appropriate atomic operations.
1009///
1010/// \returns true if the store was successfully combined away. This indicates
1011/// the caller must erase the store instruction. We have to let the caller erase
Bruce Mitchenere9ffb452015-09-12 01:17:08 +00001012/// the store instruction as otherwise there is no way to signal whether it was
Chandler Carruth816d26f2014-11-25 10:09:51 +00001013/// combined or not: IC.EraseInstFromFunction returns a null pointer.
1014static bool combineStoreToValueType(InstCombiner &IC, StoreInst &SI) {
Philip Reames6f4d0082016-05-06 22:17:01 +00001015 // FIXME: We could probably with some care handle both volatile and ordered
1016 // atomic stores here but it isn't clear that this is important.
1017 if (!SI.isUnordered())
Chandler Carruth816d26f2014-11-25 10:09:51 +00001018 return false;
Chris Lattnera65e2f72010-01-05 05:57:49 +00001019
Arnold Schwaighofer5d335552016-09-10 18:14:57 +00001020 // swifterror values can't be bitcasted.
1021 if (SI.getPointerOperand()->isSwiftError())
1022 return false;
1023
Chandler Carruth816d26f2014-11-25 10:09:51 +00001024 Value *V = SI.getValueOperand();
Jim Grosbachbdbd7342013-04-05 21:20:12 +00001025
Chandler Carruth816d26f2014-11-25 10:09:51 +00001026 // Fold away bit casts of the stored value by storing the original type.
1027 if (auto *BC = dyn_cast<BitCastInst>(V)) {
Chandler Carrutha7f247e2014-12-09 19:21:16 +00001028 V = BC->getOperand(0);
Chandler Carruth2135b972015-01-21 23:45:01 +00001029 combineStoreToNewValue(IC, SI, V);
Chandler Carruth816d26f2014-11-25 10:09:51 +00001030 return true;
Chris Lattnera65e2f72010-01-05 05:57:49 +00001031 }
1032
Arch D. Robisonbe0490a2016-04-25 22:22:39 +00001033 if (Value *U = likeBitCastFromVector(IC, V)) {
1034 combineStoreToNewValue(IC, SI, U);
1035 return true;
1036 }
1037
JF Bastienc22d2992016-04-21 19:53:39 +00001038 // FIXME: We should also canonicalize stores of vectors when their elements
1039 // are cast to other types.
Chandler Carruth816d26f2014-11-25 10:09:51 +00001040 return false;
Chris Lattnera65e2f72010-01-05 05:57:49 +00001041}
1042
Mehdi Aminib344ac92015-03-14 22:19:33 +00001043static bool unpackStoreToAggregate(InstCombiner &IC, StoreInst &SI) {
1044 // FIXME: We could probably with some care handle both volatile and atomic
1045 // stores here but it isn't clear that this is important.
1046 if (!SI.isSimple())
1047 return false;
1048
1049 Value *V = SI.getValueOperand();
1050 Type *T = V->getType();
1051
1052 if (!T->isAggregateType())
1053 return false;
1054
Mehdi Amini2668a482015-05-07 05:52:40 +00001055 if (auto *ST = dyn_cast<StructType>(T)) {
Mehdi Aminib344ac92015-03-14 22:19:33 +00001056 // If the struct only have one element, we unpack.
Mehdi Amini1c131b32015-12-15 01:44:07 +00001057 unsigned Count = ST->getNumElements();
1058 if (Count == 1) {
Mehdi Aminib344ac92015-03-14 22:19:33 +00001059 V = IC.Builder->CreateExtractValue(V, 0);
1060 combineStoreToNewValue(IC, SI, V);
1061 return true;
1062 }
Mehdi Amini1c131b32015-12-15 01:44:07 +00001063
1064 // We don't want to break loads with padding here as we'd loose
1065 // the knowledge that padding exists for the rest of the pipeline.
1066 const DataLayout &DL = IC.getDataLayout();
1067 auto *SL = DL.getStructLayout(ST);
1068 if (SL->hasPadding())
1069 return false;
1070
Amaury Sechet61a7d622016-02-17 19:21:28 +00001071 auto Align = SI.getAlignment();
1072 if (!Align)
1073 Align = DL.getABITypeAlignment(ST);
1074
NAKAMURA Takumiec6b1fc2015-12-15 09:37:31 +00001075 SmallString<16> EltName = V->getName();
1076 EltName += ".elt";
Mehdi Amini1c131b32015-12-15 01:44:07 +00001077 auto *Addr = SI.getPointerOperand();
NAKAMURA Takumiec6b1fc2015-12-15 09:37:31 +00001078 SmallString<16> AddrName = Addr->getName();
1079 AddrName += ".repack";
Amaury Sechet61a7d622016-02-17 19:21:28 +00001080
Mehdi Amini1c131b32015-12-15 01:44:07 +00001081 auto *IdxType = Type::getInt32Ty(ST->getContext());
1082 auto *Zero = ConstantInt::get(IdxType, 0);
1083 for (unsigned i = 0; i < Count; i++) {
1084 Value *Indices[2] = {
1085 Zero,
1086 ConstantInt::get(IdxType, i),
1087 };
Amaury Sechetda71cb72016-02-17 21:21:29 +00001088 auto *Ptr = IC.Builder->CreateInBoundsGEP(ST, Addr, makeArrayRef(Indices),
1089 AddrName);
Mehdi Amini1c131b32015-12-15 01:44:07 +00001090 auto *Val = IC.Builder->CreateExtractValue(V, i, EltName);
Amaury Sechet61a7d622016-02-17 19:21:28 +00001091 auto EltAlign = MinAlign(Align, SL->getElementOffset(i));
1092 IC.Builder->CreateAlignedStore(Val, Ptr, EltAlign);
Mehdi Amini1c131b32015-12-15 01:44:07 +00001093 }
1094
1095 return true;
Mehdi Aminib344ac92015-03-14 22:19:33 +00001096 }
1097
David Majnemer75364602015-05-11 05:04:27 +00001098 if (auto *AT = dyn_cast<ArrayType>(T)) {
1099 // If the array only have one element, we unpack.
Amaury Sechet3b8b2ea2016-03-02 22:36:45 +00001100 auto NumElements = AT->getNumElements();
1101 if (NumElements == 1) {
David Majnemer75364602015-05-11 05:04:27 +00001102 V = IC.Builder->CreateExtractValue(V, 0);
1103 combineStoreToNewValue(IC, SI, V);
1104 return true;
1105 }
Amaury Sechet3b8b2ea2016-03-02 22:36:45 +00001106
Davide Italianof6988d22016-10-07 21:53:09 +00001107 // Bail out if the array is too large. Ideally we would like to optimize
1108 // arrays of arbitrary size but this has a terrible impact on compile time.
1109 // The threshold here is chosen arbitrarily, maybe needs a little bit of
1110 // tuning.
1111 if (NumElements > 1024)
1112 return false;
1113
Amaury Sechet3b8b2ea2016-03-02 22:36:45 +00001114 const DataLayout &DL = IC.getDataLayout();
1115 auto EltSize = DL.getTypeAllocSize(AT->getElementType());
1116 auto Align = SI.getAlignment();
1117 if (!Align)
1118 Align = DL.getABITypeAlignment(T);
1119
1120 SmallString<16> EltName = V->getName();
1121 EltName += ".elt";
1122 auto *Addr = SI.getPointerOperand();
1123 SmallString<16> AddrName = Addr->getName();
1124 AddrName += ".repack";
1125
1126 auto *IdxType = Type::getInt64Ty(T->getContext());
1127 auto *Zero = ConstantInt::get(IdxType, 0);
1128
1129 uint64_t Offset = 0;
1130 for (uint64_t i = 0; i < NumElements; i++) {
1131 Value *Indices[2] = {
1132 Zero,
1133 ConstantInt::get(IdxType, i),
1134 };
1135 auto *Ptr = IC.Builder->CreateInBoundsGEP(AT, Addr, makeArrayRef(Indices),
1136 AddrName);
1137 auto *Val = IC.Builder->CreateExtractValue(V, i, EltName);
1138 auto EltAlign = MinAlign(Align, Offset);
1139 IC.Builder->CreateAlignedStore(Val, Ptr, EltAlign);
1140 Offset += EltSize;
1141 }
1142
1143 return true;
David Majnemer75364602015-05-11 05:04:27 +00001144 }
1145
Mehdi Aminib344ac92015-03-14 22:19:33 +00001146 return false;
1147}
1148
Chris Lattnera65e2f72010-01-05 05:57:49 +00001149/// equivalentAddressValues - Test if A and B will obviously have the same
1150/// value. This includes recognizing that %t0 and %t1 will have the same
1151/// value in code like this:
1152/// %t0 = getelementptr \@a, 0, 3
1153/// store i32 0, i32* %t0
1154/// %t1 = getelementptr \@a, 0, 3
1155/// %t2 = load i32* %t1
1156///
1157static bool equivalentAddressValues(Value *A, Value *B) {
1158 // Test if the values are trivially equivalent.
1159 if (A == B) return true;
Jim Grosbachbdbd7342013-04-05 21:20:12 +00001160
Chris Lattnera65e2f72010-01-05 05:57:49 +00001161 // Test if the values come form identical arithmetic instructions.
1162 // This uses isIdenticalToWhenDefined instead of isIdenticalTo because
1163 // its only used to compare two uses within the same basic block, which
1164 // means that they'll always either have the same value or one of them
1165 // will have an undefined value.
1166 if (isa<BinaryOperator>(A) ||
1167 isa<CastInst>(A) ||
1168 isa<PHINode>(A) ||
1169 isa<GetElementPtrInst>(A))
1170 if (Instruction *BI = dyn_cast<Instruction>(B))
1171 if (cast<Instruction>(A)->isIdenticalToWhenDefined(BI))
1172 return true;
Jim Grosbachbdbd7342013-04-05 21:20:12 +00001173
Chris Lattnera65e2f72010-01-05 05:57:49 +00001174 // Otherwise they may not be equivalent.
1175 return false;
1176}
1177
Chris Lattnera65e2f72010-01-05 05:57:49 +00001178Instruction *InstCombiner::visitStoreInst(StoreInst &SI) {
1179 Value *Val = SI.getOperand(0);
1180 Value *Ptr = SI.getOperand(1);
1181
Chandler Carruth816d26f2014-11-25 10:09:51 +00001182 // Try to canonicalize the stored type.
1183 if (combineStoreToValueType(*this, SI))
Sanjay Patel4b198802016-02-01 22:23:39 +00001184 return eraseInstFromFunction(SI);
Chandler Carruth816d26f2014-11-25 10:09:51 +00001185
Chris Lattnera65e2f72010-01-05 05:57:49 +00001186 // Attempt to improve the alignment.
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001187 unsigned KnownAlign = getOrEnforceKnownAlignment(
Justin Bogner99798402016-08-05 01:06:44 +00001188 Ptr, DL.getPrefTypeAlignment(Val->getType()), DL, &SI, &AC, &DT);
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001189 unsigned StoreAlign = SI.getAlignment();
1190 unsigned EffectiveStoreAlign =
1191 StoreAlign != 0 ? StoreAlign : DL.getABITypeAlignment(Val->getType());
Dan Gohman36196602010-08-03 18:20:32 +00001192
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001193 if (KnownAlign > EffectiveStoreAlign)
1194 SI.setAlignment(KnownAlign);
1195 else if (StoreAlign == 0)
1196 SI.setAlignment(EffectiveStoreAlign);
Chris Lattnera65e2f72010-01-05 05:57:49 +00001197
Mehdi Aminib344ac92015-03-14 22:19:33 +00001198 // Try to canonicalize the stored type.
1199 if (unpackStoreToAggregate(*this, SI))
Sanjay Patel4b198802016-02-01 22:23:39 +00001200 return eraseInstFromFunction(SI);
Mehdi Aminib344ac92015-03-14 22:19:33 +00001201
Hal Finkel847e05f2015-02-20 03:05:53 +00001202 // Replace GEP indices if possible.
1203 if (Instruction *NewGEPI = replaceGEPIdxWithZero(*this, Ptr, SI)) {
1204 Worklist.Add(NewGEPI);
1205 return &SI;
1206 }
1207
Philip Reamesd7a6cc82015-12-17 22:19:27 +00001208 // Don't hack volatile/ordered stores.
1209 // FIXME: Some bits are legal for ordered atomic stores; needs refactoring.
1210 if (!SI.isUnordered()) return nullptr;
Eli Friedman8bc586e2011-08-15 22:09:40 +00001211
1212 // If the RHS is an alloca with a single use, zapify the store, making the
1213 // alloca dead.
1214 if (Ptr->hasOneUse()) {
Jim Grosbachbdbd7342013-04-05 21:20:12 +00001215 if (isa<AllocaInst>(Ptr))
Sanjay Patel4b198802016-02-01 22:23:39 +00001216 return eraseInstFromFunction(SI);
Eli Friedman8bc586e2011-08-15 22:09:40 +00001217 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr)) {
1218 if (isa<AllocaInst>(GEP->getOperand(0))) {
1219 if (GEP->getOperand(0)->hasOneUse())
Sanjay Patel4b198802016-02-01 22:23:39 +00001220 return eraseInstFromFunction(SI);
Eli Friedman8bc586e2011-08-15 22:09:40 +00001221 }
1222 }
1223 }
1224
Chris Lattnera65e2f72010-01-05 05:57:49 +00001225 // Do really simple DSE, to catch cases where there are several consecutive
1226 // stores to the same location, separated by a few arithmetic operations. This
1227 // situation often occurs with bitfield accesses.
Duncan P. N. Exon Smith9f8aaf22015-10-13 16:59:33 +00001228 BasicBlock::iterator BBI(SI);
Chris Lattnera65e2f72010-01-05 05:57:49 +00001229 for (unsigned ScanInsts = 6; BBI != SI.getParent()->begin() && ScanInsts;
1230 --ScanInsts) {
1231 --BBI;
Victor Hernandez5f8c8c02010-01-22 19:05:05 +00001232 // Don't count debug info directives, lest they affect codegen,
1233 // and we skip pointer-to-pointer bitcasts, which are NOPs.
1234 if (isa<DbgInfoIntrinsic>(BBI) ||
Duncan Sands19d0b472010-02-16 11:11:14 +00001235 (isa<BitCastInst>(BBI) && BBI->getType()->isPointerTy())) {
Chris Lattnera65e2f72010-01-05 05:57:49 +00001236 ScanInsts++;
1237 continue;
Jim Grosbachbdbd7342013-04-05 21:20:12 +00001238 }
1239
Chris Lattnera65e2f72010-01-05 05:57:49 +00001240 if (StoreInst *PrevSI = dyn_cast<StoreInst>(BBI)) {
1241 // Prev store isn't volatile, and stores to the same location?
Philip Reamesd7a6cc82015-12-17 22:19:27 +00001242 if (PrevSI->isUnordered() && equivalentAddressValues(PrevSI->getOperand(1),
Eli Friedman8bc586e2011-08-15 22:09:40 +00001243 SI.getOperand(1))) {
Chris Lattnera65e2f72010-01-05 05:57:49 +00001244 ++NumDeadStore;
1245 ++BBI;
Sanjay Patel4b198802016-02-01 22:23:39 +00001246 eraseInstFromFunction(*PrevSI);
Chris Lattnera65e2f72010-01-05 05:57:49 +00001247 continue;
1248 }
1249 break;
1250 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +00001251
Chris Lattnera65e2f72010-01-05 05:57:49 +00001252 // If this is a load, we have to stop. However, if the loaded value is from
1253 // the pointer we're loading and is producing the pointer we're storing,
1254 // then *this* store is dead (X = load P; store X -> P).
1255 if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) {
Philip Reamesd7a6cc82015-12-17 22:19:27 +00001256 if (LI == Val && equivalentAddressValues(LI->getOperand(0), Ptr)) {
1257 assert(SI.isUnordered() && "can't eliminate ordering operation");
Sanjay Patel4b198802016-02-01 22:23:39 +00001258 return eraseInstFromFunction(SI);
Philip Reamesd7a6cc82015-12-17 22:19:27 +00001259 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +00001260
Chris Lattnera65e2f72010-01-05 05:57:49 +00001261 // Otherwise, this is a load from some other location. Stores before it
1262 // may not be dead.
1263 break;
1264 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +00001265
Chris Lattnera65e2f72010-01-05 05:57:49 +00001266 // Don't skip over loads or things that can modify memory.
1267 if (BBI->mayWriteToMemory() || BBI->mayReadFromMemory())
1268 break;
1269 }
Chris Lattnera65e2f72010-01-05 05:57:49 +00001270
1271 // store X, null -> turns into 'unreachable' in SimplifyCFG
1272 if (isa<ConstantPointerNull>(Ptr) && SI.getPointerAddressSpace() == 0) {
1273 if (!isa<UndefValue>(Val)) {
1274 SI.setOperand(0, UndefValue::get(Val->getType()));
1275 if (Instruction *U = dyn_cast<Instruction>(Val))
1276 Worklist.Add(U); // Dropped a use.
1277 }
Craig Topperf40110f2014-04-25 05:29:35 +00001278 return nullptr; // Do not modify these!
Chris Lattnera65e2f72010-01-05 05:57:49 +00001279 }
1280
1281 // store undef, Ptr -> noop
1282 if (isa<UndefValue>(Val))
Sanjay Patel4b198802016-02-01 22:23:39 +00001283 return eraseInstFromFunction(SI);
Chris Lattnera65e2f72010-01-05 05:57:49 +00001284
Chris Lattnera65e2f72010-01-05 05:57:49 +00001285 // If this store is the last instruction in the basic block (possibly
Victor Hernandez5f5abd52010-01-21 23:07:15 +00001286 // excepting debug info instructions), and if the block ends with an
1287 // unconditional branch, try to move it to the successor block.
Duncan P. N. Exon Smith9f8aaf22015-10-13 16:59:33 +00001288 BBI = SI.getIterator();
Chris Lattnera65e2f72010-01-05 05:57:49 +00001289 do {
1290 ++BBI;
Victor Hernandez5f8c8c02010-01-22 19:05:05 +00001291 } while (isa<DbgInfoIntrinsic>(BBI) ||
Duncan Sands19d0b472010-02-16 11:11:14 +00001292 (isa<BitCastInst>(BBI) && BBI->getType()->isPointerTy()));
Chris Lattnera65e2f72010-01-05 05:57:49 +00001293 if (BranchInst *BI = dyn_cast<BranchInst>(BBI))
1294 if (BI->isUnconditional())
1295 if (SimplifyStoreAtEndOfBlock(SI))
Craig Topperf40110f2014-04-25 05:29:35 +00001296 return nullptr; // xform done!
Jim Grosbachbdbd7342013-04-05 21:20:12 +00001297
Craig Topperf40110f2014-04-25 05:29:35 +00001298 return nullptr;
Chris Lattnera65e2f72010-01-05 05:57:49 +00001299}
1300
1301/// SimplifyStoreAtEndOfBlock - Turn things like:
1302/// if () { *P = v1; } else { *P = v2 }
1303/// into a phi node with a store in the successor.
1304///
1305/// Simplify things like:
1306/// *P = v1; if () { *P = v2; }
1307/// into a phi node with a store in the successor.
1308///
1309bool InstCombiner::SimplifyStoreAtEndOfBlock(StoreInst &SI) {
Philip Reames5f0e3692016-04-22 20:53:32 +00001310 assert(SI.isUnordered() &&
1311 "this code has not been auditted for volatile or ordered store case");
Justin Bognerc7e4fbe2016-08-05 01:09:48 +00001312
Chris Lattnera65e2f72010-01-05 05:57:49 +00001313 BasicBlock *StoreBB = SI.getParent();
Jim Grosbachbdbd7342013-04-05 21:20:12 +00001314
Chris Lattnera65e2f72010-01-05 05:57:49 +00001315 // Check to see if the successor block has exactly two incoming edges. If
1316 // so, see if the other predecessor contains a store to the same location.
1317 // if so, insert a PHI node (if needed) and move the stores down.
1318 BasicBlock *DestBB = StoreBB->getTerminator()->getSuccessor(0);
Jim Grosbachbdbd7342013-04-05 21:20:12 +00001319
Chris Lattnera65e2f72010-01-05 05:57:49 +00001320 // Determine whether Dest has exactly two predecessors and, if so, compute
1321 // the other predecessor.
1322 pred_iterator PI = pred_begin(DestBB);
Gabor Greif1b787df2010-07-12 15:48:26 +00001323 BasicBlock *P = *PI;
Craig Topperf40110f2014-04-25 05:29:35 +00001324 BasicBlock *OtherBB = nullptr;
Gabor Greif1b787df2010-07-12 15:48:26 +00001325
1326 if (P != StoreBB)
1327 OtherBB = P;
1328
1329 if (++PI == pred_end(DestBB))
Chris Lattnera65e2f72010-01-05 05:57:49 +00001330 return false;
Jim Grosbachbdbd7342013-04-05 21:20:12 +00001331
Gabor Greif1b787df2010-07-12 15:48:26 +00001332 P = *PI;
1333 if (P != StoreBB) {
Chris Lattnera65e2f72010-01-05 05:57:49 +00001334 if (OtherBB)
1335 return false;
Gabor Greif1b787df2010-07-12 15:48:26 +00001336 OtherBB = P;
Chris Lattnera65e2f72010-01-05 05:57:49 +00001337 }
1338 if (++PI != pred_end(DestBB))
1339 return false;
1340
1341 // Bail out if all the relevant blocks aren't distinct (this can happen,
1342 // for example, if SI is in an infinite loop)
1343 if (StoreBB == DestBB || OtherBB == DestBB)
1344 return false;
1345
1346 // Verify that the other block ends in a branch and is not otherwise empty.
Duncan P. N. Exon Smith9f8aaf22015-10-13 16:59:33 +00001347 BasicBlock::iterator BBI(OtherBB->getTerminator());
Chris Lattnera65e2f72010-01-05 05:57:49 +00001348 BranchInst *OtherBr = dyn_cast<BranchInst>(BBI);
1349 if (!OtherBr || BBI == OtherBB->begin())
1350 return false;
Jim Grosbachbdbd7342013-04-05 21:20:12 +00001351
Chris Lattnera65e2f72010-01-05 05:57:49 +00001352 // If the other block ends in an unconditional branch, check for the 'if then
1353 // else' case. there is an instruction before the branch.
Craig Topperf40110f2014-04-25 05:29:35 +00001354 StoreInst *OtherStore = nullptr;
Chris Lattnera65e2f72010-01-05 05:57:49 +00001355 if (OtherBr->isUnconditional()) {
1356 --BBI;
1357 // Skip over debugging info.
Victor Hernandez5f8c8c02010-01-22 19:05:05 +00001358 while (isa<DbgInfoIntrinsic>(BBI) ||
Duncan Sands19d0b472010-02-16 11:11:14 +00001359 (isa<BitCastInst>(BBI) && BBI->getType()->isPointerTy())) {
Chris Lattnera65e2f72010-01-05 05:57:49 +00001360 if (BBI==OtherBB->begin())
1361 return false;
1362 --BBI;
1363 }
Eli Friedman8bc586e2011-08-15 22:09:40 +00001364 // If this isn't a store, isn't a store to the same location, or is not the
1365 // right kind of store, bail out.
Chris Lattnera65e2f72010-01-05 05:57:49 +00001366 OtherStore = dyn_cast<StoreInst>(BBI);
1367 if (!OtherStore || OtherStore->getOperand(1) != SI.getOperand(1) ||
Eli Friedman8bc586e2011-08-15 22:09:40 +00001368 !SI.isSameOperationAs(OtherStore))
Chris Lattnera65e2f72010-01-05 05:57:49 +00001369 return false;
1370 } else {
1371 // Otherwise, the other block ended with a conditional branch. If one of the
1372 // destinations is StoreBB, then we have the if/then case.
Jim Grosbachbdbd7342013-04-05 21:20:12 +00001373 if (OtherBr->getSuccessor(0) != StoreBB &&
Chris Lattnera65e2f72010-01-05 05:57:49 +00001374 OtherBr->getSuccessor(1) != StoreBB)
1375 return false;
Jim Grosbachbdbd7342013-04-05 21:20:12 +00001376
Chris Lattnera65e2f72010-01-05 05:57:49 +00001377 // Okay, we know that OtherBr now goes to Dest and StoreBB, so this is an
1378 // if/then triangle. See if there is a store to the same ptr as SI that
1379 // lives in OtherBB.
1380 for (;; --BBI) {
1381 // Check to see if we find the matching store.
1382 if ((OtherStore = dyn_cast<StoreInst>(BBI))) {
1383 if (OtherStore->getOperand(1) != SI.getOperand(1) ||
Eli Friedman8bc586e2011-08-15 22:09:40 +00001384 !SI.isSameOperationAs(OtherStore))
Chris Lattnera65e2f72010-01-05 05:57:49 +00001385 return false;
1386 break;
1387 }
1388 // If we find something that may be using or overwriting the stored
1389 // value, or if we run out of instructions, we can't do the xform.
1390 if (BBI->mayReadFromMemory() || BBI->mayWriteToMemory() ||
1391 BBI == OtherBB->begin())
1392 return false;
1393 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +00001394
Chris Lattnera65e2f72010-01-05 05:57:49 +00001395 // In order to eliminate the store in OtherBr, we have to
1396 // make sure nothing reads or overwrites the stored value in
1397 // StoreBB.
1398 for (BasicBlock::iterator I = StoreBB->begin(); &*I != &SI; ++I) {
1399 // FIXME: This should really be AA driven.
1400 if (I->mayReadFromMemory() || I->mayWriteToMemory())
1401 return false;
1402 }
1403 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +00001404
Chris Lattnera65e2f72010-01-05 05:57:49 +00001405 // Insert a PHI node now if we need it.
1406 Value *MergedVal = OtherStore->getOperand(0);
1407 if (MergedVal != SI.getOperand(0)) {
Jay Foad52131342011-03-30 11:28:46 +00001408 PHINode *PN = PHINode::Create(MergedVal->getType(), 2, "storemerge");
Chris Lattnera65e2f72010-01-05 05:57:49 +00001409 PN->addIncoming(SI.getOperand(0), SI.getParent());
1410 PN->addIncoming(OtherStore->getOperand(0), OtherBB);
1411 MergedVal = InsertNewInstBefore(PN, DestBB->front());
1412 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +00001413
Chris Lattnera65e2f72010-01-05 05:57:49 +00001414 // Advance to a place where it is safe to insert the new store and
1415 // insert it.
Bill Wendling8ddfc092011-08-16 20:45:24 +00001416 BBI = DestBB->getFirstInsertionPt();
Eli Friedman35211c62011-05-27 00:19:40 +00001417 StoreInst *NewSI = new StoreInst(MergedVal, SI.getOperand(1),
Eli Friedman8bc586e2011-08-15 22:09:40 +00001418 SI.isVolatile(),
1419 SI.getAlignment(),
1420 SI.getOrdering(),
1421 SI.getSynchScope());
Eli Friedman35211c62011-05-27 00:19:40 +00001422 InsertNewInstBefore(NewSI, *BBI);
Jim Grosbachbdbd7342013-04-05 21:20:12 +00001423 NewSI->setDebugLoc(OtherStore->getDebugLoc());
Eli Friedman35211c62011-05-27 00:19:40 +00001424
Hal Finkelcc39b672014-07-24 12:16:19 +00001425 // If the two stores had AA tags, merge them.
1426 AAMDNodes AATags;
1427 SI.getAAMetadata(AATags);
1428 if (AATags) {
1429 OtherStore->getAAMetadata(AATags, /* Merge = */ true);
1430 NewSI->setAAMetadata(AATags);
1431 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +00001432
Chris Lattnera65e2f72010-01-05 05:57:49 +00001433 // Nuke the old stores.
Sanjay Patel4b198802016-02-01 22:23:39 +00001434 eraseInstFromFunction(SI);
1435 eraseInstFromFunction(*OtherStore);
Chris Lattnera65e2f72010-01-05 05:57:49 +00001436 return true;
1437}