blob: 91bfe6c5c8257994eb8777fd3bb87809b97f6ad2 [file] [log] [blame]
Chris Lattnerde1fede2010-01-05 05:31:55 +00001//===- InstCombinePHI.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 visitPHINode function.
11//
12//===----------------------------------------------------------------------===//
13
Chandler Carrutha9174582015-01-22 05:25:13 +000014#include "InstCombineInternal.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000015#include "llvm/ADT/STLExtras.h"
16#include "llvm/ADT/SmallPtrSet.h"
Duncan Sands4581ddc2010-11-14 13:30:18 +000017#include "llvm/Analysis/InstructionSimplify.h"
Jun Bum Lim339e9722016-02-11 15:50:07 +000018#include "llvm/Analysis/ValueTracking.h"
19#include "llvm/IR/PatternMatch.h"
Akira Hatanakaf6afd112015-09-23 18:40:57 +000020#include "llvm/Transforms/Utils/Local.h"
Robert Lougher2428a402016-12-14 17:49:19 +000021#include "llvm/IR/DebugInfo.h"
Chris Lattnerde1fede2010-01-05 05:31:55 +000022using namespace llvm;
Jun Bum Lim339e9722016-02-11 15:50:07 +000023using namespace llvm::PatternMatch;
Chris Lattnerde1fede2010-01-05 05:31:55 +000024
Chandler Carruth964daaa2014-04-22 02:55:47 +000025#define DEBUG_TYPE "instcombine"
26
Robert Lougher2428a402016-12-14 17:49:19 +000027/// The PHI arguments will be folded into a single operation with a PHI node
28/// as input. The debug location of the single operation will be the merged
29/// locations of the original PHI node arguments.
30DebugLoc InstCombiner::PHIArgMergedDebugLoc(PHINode &PN) {
31 auto *FirstInst = cast<Instruction>(PN.getIncomingValue(0));
32 DILocation *Loc = FirstInst->getDebugLoc();
33
34 for (unsigned i = 1; i != PN.getNumIncomingValues(); ++i) {
35 auto *I = cast<Instruction>(PN.getIncomingValue(i));
36 Loc = DILocation::getMergedLocation(Loc, I->getDebugLoc());
37 }
38
39 return Loc;
40}
41
Sanjay Patel9b7e6772015-06-23 23:05:08 +000042/// If we have something like phi [add (a,b), add(a,c)] and if a/b/c and the
43/// adds all have a single use, turn this into a phi and a single binop.
Chris Lattnerde1fede2010-01-05 05:31:55 +000044Instruction *InstCombiner::FoldPHIArgBinOpIntoPHI(PHINode &PN) {
45 Instruction *FirstInst = cast<Instruction>(PN.getIncomingValue(0));
46 assert(isa<BinaryOperator>(FirstInst) || isa<CmpInst>(FirstInst));
47 unsigned Opc = FirstInst->getOpcode();
48 Value *LHSVal = FirstInst->getOperand(0);
49 Value *RHSVal = FirstInst->getOperand(1);
Jim Grosbachbdbd7342013-04-05 21:20:12 +000050
Chris Lattner229907c2011-07-18 04:54:35 +000051 Type *LHSType = LHSVal->getType();
52 Type *RHSType = RHSVal->getType();
Jim Grosbachbdbd7342013-04-05 21:20:12 +000053
Chris Lattnerde1fede2010-01-05 05:31:55 +000054 // Scan to see if all operands are the same opcode, and all have one use.
55 for (unsigned i = 1; i != PN.getNumIncomingValues(); ++i) {
56 Instruction *I = dyn_cast<Instruction>(PN.getIncomingValue(i));
57 if (!I || I->getOpcode() != Opc || !I->hasOneUse() ||
58 // Verify type of the LHS matches so we don't fold cmp's of different
Chris Lattnera8fed472011-02-17 23:01:49 +000059 // types.
Chris Lattnerde1fede2010-01-05 05:31:55 +000060 I->getOperand(0)->getType() != LHSType ||
61 I->getOperand(1)->getType() != RHSType)
Craig Topperf40110f2014-04-25 05:29:35 +000062 return nullptr;
Chris Lattnerde1fede2010-01-05 05:31:55 +000063
64 // If they are CmpInst instructions, check their predicates
Chris Lattnera8fed472011-02-17 23:01:49 +000065 if (CmpInst *CI = dyn_cast<CmpInst>(I))
66 if (CI->getPredicate() != cast<CmpInst>(FirstInst)->getPredicate())
Craig Topperf40110f2014-04-25 05:29:35 +000067 return nullptr;
Jim Grosbachbdbd7342013-04-05 21:20:12 +000068
Chris Lattnerde1fede2010-01-05 05:31:55 +000069 // Keep track of which operand needs a phi node.
Craig Topperf40110f2014-04-25 05:29:35 +000070 if (I->getOperand(0) != LHSVal) LHSVal = nullptr;
71 if (I->getOperand(1) != RHSVal) RHSVal = nullptr;
Chris Lattnerde1fede2010-01-05 05:31:55 +000072 }
73
74 // If both LHS and RHS would need a PHI, don't do this transformation,
75 // because it would increase the number of PHIs entering the block,
76 // which leads to higher register pressure. This is especially
77 // bad when the PHIs are in the header of a loop.
78 if (!LHSVal && !RHSVal)
Craig Topperf40110f2014-04-25 05:29:35 +000079 return nullptr;
Jim Grosbachbdbd7342013-04-05 21:20:12 +000080
Chris Lattnerde1fede2010-01-05 05:31:55 +000081 // Otherwise, this is safe to transform!
Jim Grosbachbdbd7342013-04-05 21:20:12 +000082
Chris Lattnerde1fede2010-01-05 05:31:55 +000083 Value *InLHS = FirstInst->getOperand(0);
84 Value *InRHS = FirstInst->getOperand(1);
Craig Topperf40110f2014-04-25 05:29:35 +000085 PHINode *NewLHS = nullptr, *NewRHS = nullptr;
86 if (!LHSVal) {
Jay Foad52131342011-03-30 11:28:46 +000087 NewLHS = PHINode::Create(LHSType, PN.getNumIncomingValues(),
Chris Lattnerde1fede2010-01-05 05:31:55 +000088 FirstInst->getOperand(0)->getName() + ".pn");
Chris Lattnerde1fede2010-01-05 05:31:55 +000089 NewLHS->addIncoming(InLHS, PN.getIncomingBlock(0));
90 InsertNewInstBefore(NewLHS, PN);
91 LHSVal = NewLHS;
92 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +000093
Craig Topperf40110f2014-04-25 05:29:35 +000094 if (!RHSVal) {
Jay Foad52131342011-03-30 11:28:46 +000095 NewRHS = PHINode::Create(RHSType, PN.getNumIncomingValues(),
Chris Lattnerde1fede2010-01-05 05:31:55 +000096 FirstInst->getOperand(1)->getName() + ".pn");
Chris Lattnerde1fede2010-01-05 05:31:55 +000097 NewRHS->addIncoming(InRHS, PN.getIncomingBlock(0));
98 InsertNewInstBefore(NewRHS, PN);
99 RHSVal = NewRHS;
100 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000101
Chris Lattnerde1fede2010-01-05 05:31:55 +0000102 // Add all operands to the new PHIs.
103 if (NewLHS || NewRHS) {
104 for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
105 Instruction *InInst = cast<Instruction>(PN.getIncomingValue(i));
106 if (NewLHS) {
107 Value *NewInLHS = InInst->getOperand(0);
108 NewLHS->addIncoming(NewInLHS, PN.getIncomingBlock(i));
109 }
110 if (NewRHS) {
111 Value *NewInRHS = InInst->getOperand(1);
112 NewRHS->addIncoming(NewInRHS, PN.getIncomingBlock(i));
113 }
114 }
115 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000116
Eli Friedman35211c62011-05-27 00:19:40 +0000117 if (CmpInst *CIOp = dyn_cast<CmpInst>(FirstInst)) {
118 CmpInst *NewCI = CmpInst::Create(CIOp->getOpcode(), CIOp->getPredicate(),
119 LHSVal, RHSVal);
120 NewCI->setDebugLoc(FirstInst->getDebugLoc());
121 return NewCI;
122 }
123
Chris Lattnera8fed472011-02-17 23:01:49 +0000124 BinaryOperator *BinOp = cast<BinaryOperator>(FirstInst);
125 BinaryOperator *NewBinOp =
126 BinaryOperator::Create(BinOp->getOpcode(), LHSVal, RHSVal);
Silviu Barangae985c762016-04-22 11:21:36 +0000127
128 NewBinOp->copyIRFlags(PN.getIncomingValue(0));
129
130 for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i)
131 NewBinOp->andIRFlags(PN.getIncomingValue(i));
132
Robert Lougher2428a402016-12-14 17:49:19 +0000133 NewBinOp->setDebugLoc(PHIArgMergedDebugLoc(PN));
Chris Lattnera8fed472011-02-17 23:01:49 +0000134 return NewBinOp;
Chris Lattnerde1fede2010-01-05 05:31:55 +0000135}
136
137Instruction *InstCombiner::FoldPHIArgGEPIntoPHI(PHINode &PN) {
138 GetElementPtrInst *FirstInst =cast<GetElementPtrInst>(PN.getIncomingValue(0));
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000139
140 SmallVector<Value*, 16> FixedOperands(FirstInst->op_begin(),
Chris Lattnerde1fede2010-01-05 05:31:55 +0000141 FirstInst->op_end());
142 // This is true if all GEP bases are allocas and if all indices into them are
143 // constants.
144 bool AllBasePointersAreAllocas = true;
145
146 // We don't want to replace this phi if the replacement would require
147 // more than one phi, which leads to higher register pressure. This is
148 // especially bad when the PHIs are in the header of a loop.
149 bool NeededPhi = false;
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000150
Chris Lattnerabb8eb22011-02-17 22:21:26 +0000151 bool AllInBounds = true;
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000152
Chris Lattnerde1fede2010-01-05 05:31:55 +0000153 // Scan to see if all operands are the same opcode, and all have one use.
154 for (unsigned i = 1; i != PN.getNumIncomingValues(); ++i) {
155 GetElementPtrInst *GEP= dyn_cast<GetElementPtrInst>(PN.getIncomingValue(i));
156 if (!GEP || !GEP->hasOneUse() || GEP->getType() != FirstInst->getType() ||
157 GEP->getNumOperands() != FirstInst->getNumOperands())
Craig Topperf40110f2014-04-25 05:29:35 +0000158 return nullptr;
Chris Lattnerde1fede2010-01-05 05:31:55 +0000159
Chris Lattnerabb8eb22011-02-17 22:21:26 +0000160 AllInBounds &= GEP->isInBounds();
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000161
Chris Lattnerde1fede2010-01-05 05:31:55 +0000162 // Keep track of whether or not all GEPs are of alloca pointers.
163 if (AllBasePointersAreAllocas &&
164 (!isa<AllocaInst>(GEP->getOperand(0)) ||
165 !GEP->hasAllConstantIndices()))
166 AllBasePointersAreAllocas = false;
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000167
Chris Lattnerde1fede2010-01-05 05:31:55 +0000168 // Compare the operand lists.
169 for (unsigned op = 0, e = FirstInst->getNumOperands(); op != e; ++op) {
170 if (FirstInst->getOperand(op) == GEP->getOperand(op))
171 continue;
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000172
Chris Lattnerde1fede2010-01-05 05:31:55 +0000173 // Don't merge two GEPs when two operands differ (introducing phi nodes)
174 // if one of the PHIs has a constant for the index. The index may be
175 // substantially cheaper to compute for the constants, so making it a
176 // variable index could pessimize the path. This also handles the case
177 // for struct indices, which must always be constant.
178 if (isa<ConstantInt>(FirstInst->getOperand(op)) ||
179 isa<ConstantInt>(GEP->getOperand(op)))
Craig Topperf40110f2014-04-25 05:29:35 +0000180 return nullptr;
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000181
Chris Lattnerde1fede2010-01-05 05:31:55 +0000182 if (FirstInst->getOperand(op)->getType() !=GEP->getOperand(op)->getType())
Craig Topperf40110f2014-04-25 05:29:35 +0000183 return nullptr;
Chris Lattnerde1fede2010-01-05 05:31:55 +0000184
185 // If we already needed a PHI for an earlier operand, and another operand
186 // also requires a PHI, we'd be introducing more PHIs than we're
187 // eliminating, which increases register pressure on entry to the PHI's
188 // block.
189 if (NeededPhi)
Craig Topperf40110f2014-04-25 05:29:35 +0000190 return nullptr;
Chris Lattnerde1fede2010-01-05 05:31:55 +0000191
Craig Topperf40110f2014-04-25 05:29:35 +0000192 FixedOperands[op] = nullptr; // Needs a PHI.
Chris Lattnerde1fede2010-01-05 05:31:55 +0000193 NeededPhi = true;
194 }
195 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000196
Chris Lattnerde1fede2010-01-05 05:31:55 +0000197 // If all of the base pointers of the PHI'd GEPs are from allocas, don't
198 // bother doing this transformation. At best, this will just save a bit of
199 // offset calculation, but all the predecessors will have to materialize the
200 // stack address into a register anyway. We'd actually rather *clone* the
201 // load up into the predecessors so that we have a load of a gep of an alloca,
202 // which can usually all be folded into the load.
203 if (AllBasePointersAreAllocas)
Craig Topperf40110f2014-04-25 05:29:35 +0000204 return nullptr;
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000205
Chris Lattnerde1fede2010-01-05 05:31:55 +0000206 // Otherwise, this is safe to transform. Insert PHI nodes for each operand
207 // that is variable.
208 SmallVector<PHINode*, 16> OperandPhis(FixedOperands.size());
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000209
Chris Lattnerde1fede2010-01-05 05:31:55 +0000210 bool HasAnyPHIs = false;
211 for (unsigned i = 0, e = FixedOperands.size(); i != e; ++i) {
212 if (FixedOperands[i]) continue; // operand doesn't need a phi.
213 Value *FirstOp = FirstInst->getOperand(i);
Jay Foad52131342011-03-30 11:28:46 +0000214 PHINode *NewPN = PHINode::Create(FirstOp->getType(), e,
Chris Lattnerde1fede2010-01-05 05:31:55 +0000215 FirstOp->getName()+".pn");
216 InsertNewInstBefore(NewPN, PN);
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000217
Chris Lattnerde1fede2010-01-05 05:31:55 +0000218 NewPN->addIncoming(FirstOp, PN.getIncomingBlock(0));
219 OperandPhis[i] = NewPN;
220 FixedOperands[i] = NewPN;
221 HasAnyPHIs = true;
222 }
223
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000224
Chris Lattnerde1fede2010-01-05 05:31:55 +0000225 // Add all operands to the new PHIs.
226 if (HasAnyPHIs) {
227 for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
228 GetElementPtrInst *InGEP =cast<GetElementPtrInst>(PN.getIncomingValue(i));
229 BasicBlock *InBB = PN.getIncomingBlock(i);
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000230
Chris Lattnerde1fede2010-01-05 05:31:55 +0000231 for (unsigned op = 0, e = OperandPhis.size(); op != e; ++op)
232 if (PHINode *OpPhi = OperandPhis[op])
233 OpPhi->addIncoming(InGEP->getOperand(op), InBB);
234 }
235 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000236
Chris Lattnerde1fede2010-01-05 05:31:55 +0000237 Value *Base = FixedOperands[0];
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000238 GetElementPtrInst *NewGEP =
David Blaikie741c8f82015-03-14 01:53:18 +0000239 GetElementPtrInst::Create(FirstInst->getSourceElementType(), Base,
240 makeArrayRef(FixedOperands).slice(1));
Chris Lattner75ae5a42011-02-17 22:32:54 +0000241 if (AllInBounds) NewGEP->setIsInBounds();
Eli Friedman35211c62011-05-27 00:19:40 +0000242 NewGEP->setDebugLoc(FirstInst->getDebugLoc());
Chris Lattnerabb8eb22011-02-17 22:21:26 +0000243 return NewGEP;
Chris Lattnerde1fede2010-01-05 05:31:55 +0000244}
245
246
Sanjay Patel9b7e6772015-06-23 23:05:08 +0000247/// Return true if we know that it is safe to sink the load out of the block
248/// that defines it. This means that it must be obvious the value of the load is
249/// not changed from the point of the load to the end of the block it is in.
Chris Lattnerde1fede2010-01-05 05:31:55 +0000250///
Chris Lattner0ab5e2c2011-04-15 05:18:47 +0000251/// Finally, it is safe, but not profitable, to sink a load targeting a
Chris Lattnerde1fede2010-01-05 05:31:55 +0000252/// non-address-taken alloca. Doing so will cause us to not promote the alloca
253/// to a register.
254static bool isSafeAndProfitableToSinkLoad(LoadInst *L) {
Duncan P. N. Exon Smith9f8aaf22015-10-13 16:59:33 +0000255 BasicBlock::iterator BBI = L->getIterator(), E = L->getParent()->end();
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000256
Chris Lattnerde1fede2010-01-05 05:31:55 +0000257 for (++BBI; BBI != E; ++BBI)
258 if (BBI->mayWriteToMemory())
259 return false;
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000260
Chris Lattnerde1fede2010-01-05 05:31:55 +0000261 // Check for non-address taken alloca. If not address-taken already, it isn't
262 // profitable to do this xform.
263 if (AllocaInst *AI = dyn_cast<AllocaInst>(L->getOperand(0))) {
264 bool isAddressTaken = false;
Chandler Carruthcdf47882014-03-09 03:16:01 +0000265 for (User *U : AI->users()) {
Gabor Greif96fedcb2010-07-12 14:15:58 +0000266 if (isa<LoadInst>(U)) continue;
267 if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
Chris Lattnerde1fede2010-01-05 05:31:55 +0000268 // If storing TO the alloca, then the address isn't taken.
269 if (SI->getOperand(1) == AI) continue;
270 }
271 isAddressTaken = true;
272 break;
273 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000274
Chris Lattnerde1fede2010-01-05 05:31:55 +0000275 if (!isAddressTaken && AI->isStaticAlloca())
276 return false;
277 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000278
Chris Lattnerde1fede2010-01-05 05:31:55 +0000279 // If this load is a load from a GEP with a constant offset from an alloca,
280 // then we don't want to sink it. In its present form, it will be
281 // load [constant stack offset]. Sinking it will cause us to have to
282 // materialize the stack addresses in each predecessor in a register only to
283 // do a shared load from register in the successor.
284 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(L->getOperand(0)))
285 if (AllocaInst *AI = dyn_cast<AllocaInst>(GEP->getOperand(0)))
286 if (AI->isStaticAlloca() && GEP->hasAllConstantIndices())
287 return false;
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000288
Chris Lattnerde1fede2010-01-05 05:31:55 +0000289 return true;
290}
291
292Instruction *InstCombiner::FoldPHIArgLoadIntoPHI(PHINode &PN) {
293 LoadInst *FirstLI = cast<LoadInst>(PN.getIncomingValue(0));
Eli Friedman8bc586e2011-08-15 22:09:40 +0000294
295 // FIXME: This is overconservative; this transform is allowed in some cases
296 // for atomic operations.
297 if (FirstLI->isAtomic())
Craig Topperf40110f2014-04-25 05:29:35 +0000298 return nullptr;
Eli Friedman8bc586e2011-08-15 22:09:40 +0000299
Chris Lattnerde1fede2010-01-05 05:31:55 +0000300 // When processing loads, we need to propagate two bits of information to the
301 // sunk load: whether it is volatile, and what its alignment is. We currently
302 // don't sink loads when some have their alignment specified and some don't.
303 // visitLoadInst will propagate an alignment onto the load when TD is around,
304 // and if TD isn't around, we can't handle the mixed case.
305 bool isVolatile = FirstLI->isVolatile();
306 unsigned LoadAlignment = FirstLI->getAlignment();
Chris Lattnerf6befff2010-03-05 18:53:28 +0000307 unsigned LoadAddrSpace = FirstLI->getPointerAddressSpace();
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000308
Chris Lattnerde1fede2010-01-05 05:31:55 +0000309 // We can't sink the load if the loaded value could be modified between the
310 // load and the PHI.
311 if (FirstLI->getParent() != PN.getIncomingBlock(0) ||
312 !isSafeAndProfitableToSinkLoad(FirstLI))
Craig Topperf40110f2014-04-25 05:29:35 +0000313 return nullptr;
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000314
Chris Lattnerde1fede2010-01-05 05:31:55 +0000315 // If the PHI is of volatile loads and the load block has multiple
316 // successors, sinking it would remove a load of the volatile value from
317 // the path through the other successor.
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000318 if (isVolatile &&
Chris Lattnerde1fede2010-01-05 05:31:55 +0000319 FirstLI->getParent()->getTerminator()->getNumSuccessors() != 1)
Craig Topperf40110f2014-04-25 05:29:35 +0000320 return nullptr;
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000321
Chris Lattnerde1fede2010-01-05 05:31:55 +0000322 // Check to see if all arguments are the same operation.
323 for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
324 LoadInst *LI = dyn_cast<LoadInst>(PN.getIncomingValue(i));
325 if (!LI || !LI->hasOneUse())
Craig Topperf40110f2014-04-25 05:29:35 +0000326 return nullptr;
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000327
328 // We can't sink the load if the loaded value could be modified between
Chris Lattnerde1fede2010-01-05 05:31:55 +0000329 // the load and the PHI.
330 if (LI->isVolatile() != isVolatile ||
331 LI->getParent() != PN.getIncomingBlock(i) ||
Chris Lattnerf6befff2010-03-05 18:53:28 +0000332 LI->getPointerAddressSpace() != LoadAddrSpace ||
Chris Lattnerde1fede2010-01-05 05:31:55 +0000333 !isSafeAndProfitableToSinkLoad(LI))
Craig Topperf40110f2014-04-25 05:29:35 +0000334 return nullptr;
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000335
Chris Lattnerde1fede2010-01-05 05:31:55 +0000336 // If some of the loads have an alignment specified but not all of them,
337 // we can't do the transformation.
338 if ((LoadAlignment != 0) != (LI->getAlignment() != 0))
Craig Topperf40110f2014-04-25 05:29:35 +0000339 return nullptr;
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000340
Chris Lattnerde1fede2010-01-05 05:31:55 +0000341 LoadAlignment = std::min(LoadAlignment, LI->getAlignment());
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000342
Chris Lattnerde1fede2010-01-05 05:31:55 +0000343 // If the PHI is of volatile loads and the load block has multiple
344 // successors, sinking it would remove a load of the volatile value from
345 // the path through the other successor.
346 if (isVolatile &&
347 LI->getParent()->getTerminator()->getNumSuccessors() != 1)
Craig Topperf40110f2014-04-25 05:29:35 +0000348 return nullptr;
Chris Lattnerde1fede2010-01-05 05:31:55 +0000349 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000350
Chris Lattnerde1fede2010-01-05 05:31:55 +0000351 // Okay, they are all the same operation. Create a new PHI node of the
352 // correct type, and PHI together all of the LHS's of the instructions.
353 PHINode *NewPN = PHINode::Create(FirstLI->getOperand(0)->getType(),
Jay Foad52131342011-03-30 11:28:46 +0000354 PN.getNumIncomingValues(),
Chris Lattnerde1fede2010-01-05 05:31:55 +0000355 PN.getName()+".in");
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000356
Chris Lattnerde1fede2010-01-05 05:31:55 +0000357 Value *InVal = FirstLI->getOperand(0);
358 NewPN->addIncoming(InVal, PN.getIncomingBlock(0));
Akira Hatanakaf6afd112015-09-23 18:40:57 +0000359 LoadInst *NewLI = new LoadInst(NewPN, "", isVolatile, LoadAlignment);
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000360
Akira Hatanakaf6afd112015-09-23 18:40:57 +0000361 unsigned KnownIDs[] = {
362 LLVMContext::MD_tbaa,
363 LLVMContext::MD_range,
364 LLVMContext::MD_invariant_load,
365 LLVMContext::MD_alias_scope,
366 LLVMContext::MD_noalias,
Artur Pilipenko5c5011d2015-11-02 17:53:51 +0000367 LLVMContext::MD_nonnull,
368 LLVMContext::MD_align,
369 LLVMContext::MD_dereferenceable,
370 LLVMContext::MD_dereferenceable_or_null,
Akira Hatanakaf6afd112015-09-23 18:40:57 +0000371 };
372
373 for (unsigned ID : KnownIDs)
374 NewLI->setMetadata(ID, FirstLI->getMetadata(ID));
375
376 // Add all operands to the new PHI and combine TBAA metadata.
Chris Lattnerde1fede2010-01-05 05:31:55 +0000377 for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
Akira Hatanakaf6afd112015-09-23 18:40:57 +0000378 LoadInst *LI = cast<LoadInst>(PN.getIncomingValue(i));
379 combineMetadata(NewLI, LI, KnownIDs);
380 Value *NewInVal = LI->getOperand(0);
Chris Lattnerde1fede2010-01-05 05:31:55 +0000381 if (NewInVal != InVal)
Craig Topperf40110f2014-04-25 05:29:35 +0000382 InVal = nullptr;
Chris Lattnerde1fede2010-01-05 05:31:55 +0000383 NewPN->addIncoming(NewInVal, PN.getIncomingBlock(i));
384 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000385
Chris Lattnerde1fede2010-01-05 05:31:55 +0000386 if (InVal) {
387 // The new PHI unions all of the same values together. This is really
388 // common, so we handle it intelligently here for compile-time speed.
Akira Hatanakaf6afd112015-09-23 18:40:57 +0000389 NewLI->setOperand(0, InVal);
Chris Lattnerde1fede2010-01-05 05:31:55 +0000390 delete NewPN;
391 } else {
392 InsertNewInstBefore(NewPN, PN);
Chris Lattnerde1fede2010-01-05 05:31:55 +0000393 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000394
Chris Lattnerde1fede2010-01-05 05:31:55 +0000395 // If this was a volatile load that we are merging, make sure to loop through
396 // and mark all the input loads as non-volatile. If we don't do this, we will
397 // insert a new volatile load and the old ones will not be deletable.
398 if (isVolatile)
Pete Cooper833f34d2015-05-12 20:05:31 +0000399 for (Value *IncValue : PN.incoming_values())
400 cast<LoadInst>(IncValue)->setVolatile(false);
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000401
Eli Friedman35211c62011-05-27 00:19:40 +0000402 NewLI->setDebugLoc(FirstLI->getDebugLoc());
403 return NewLI;
Chris Lattnerde1fede2010-01-05 05:31:55 +0000404}
405
Sanjay Patel95334072015-09-27 20:34:31 +0000406/// TODO: This function could handle other cast types, but then it might
407/// require special-casing a cast from the 'i1' type. See the comment in
408/// FoldPHIArgOpIntoPHI() about pessimizing illegal integer types.
409Instruction *InstCombiner::FoldPHIArgZextsIntoPHI(PHINode &Phi) {
David Majnemereafa28a2015-11-07 00:52:53 +0000410 // We cannot create a new instruction after the PHI if the terminator is an
411 // EHPad because there is no valid insertion point.
412 if (TerminatorInst *TI = Phi.getParent()->getTerminator())
413 if (TI->isEHPad())
414 return nullptr;
415
Sanjay Patel95334072015-09-27 20:34:31 +0000416 // Early exit for the common case of a phi with two operands. These are
417 // handled elsewhere. See the comment below where we check the count of zexts
418 // and constants for more details.
419 unsigned NumIncomingValues = Phi.getNumIncomingValues();
420 if (NumIncomingValues < 3)
421 return nullptr;
Chris Lattnerde1fede2010-01-05 05:31:55 +0000422
Sanjay Patel95334072015-09-27 20:34:31 +0000423 // Find the narrower type specified by the first zext.
424 Type *NarrowType = nullptr;
425 for (Value *V : Phi.incoming_values()) {
426 if (auto *Zext = dyn_cast<ZExtInst>(V)) {
427 NarrowType = Zext->getSrcTy();
428 break;
429 }
430 }
431 if (!NarrowType)
432 return nullptr;
433
434 // Walk the phi operands checking that we only have zexts or constants that
435 // we can shrink for free. Store the new operands for the new phi.
436 SmallVector<Value *, 4> NewIncoming;
437 unsigned NumZexts = 0;
438 unsigned NumConsts = 0;
439 for (Value *V : Phi.incoming_values()) {
440 if (auto *Zext = dyn_cast<ZExtInst>(V)) {
441 // All zexts must be identical and have one use.
442 if (Zext->getSrcTy() != NarrowType || !Zext->hasOneUse())
443 return nullptr;
444 NewIncoming.push_back(Zext->getOperand(0));
445 NumZexts++;
446 } else if (auto *C = dyn_cast<Constant>(V)) {
447 // Make sure that constants can fit in the new type.
448 Constant *Trunc = ConstantExpr::getTrunc(C, NarrowType);
449 if (ConstantExpr::getZExt(Trunc, C->getType()) != C)
450 return nullptr;
451 NewIncoming.push_back(Trunc);
452 NumConsts++;
453 } else {
454 // If it's not a cast or a constant, bail out.
455 return nullptr;
456 }
457 }
458
459 // The more common cases of a phi with no constant operands or just one
460 // variable operand are handled by FoldPHIArgOpIntoPHI() and FoldOpIntoPhi()
461 // respectively. FoldOpIntoPhi() wants to do the opposite transform that is
462 // performed here. It tries to replicate a cast in the phi operand's basic
463 // block to expose other folding opportunities. Thus, InstCombine will
464 // infinite loop without this check.
465 if (NumConsts == 0 || NumZexts < 2)
466 return nullptr;
467
468 // All incoming values are zexts or constants that are safe to truncate.
469 // Create a new phi node of the narrow type, phi together all of the new
470 // operands, and zext the result back to the original type.
471 PHINode *NewPhi = PHINode::Create(NarrowType, NumIncomingValues,
472 Phi.getName() + ".shrunk");
473 for (unsigned i = 0; i != NumIncomingValues; ++i)
474 NewPhi->addIncoming(NewIncoming[i], Phi.getIncomingBlock(i));
475
476 InsertNewInstBefore(NewPhi, Phi);
477 return CastInst::CreateZExtOrBitCast(NewPhi, Phi.getType());
478}
Chris Lattnerde1fede2010-01-05 05:31:55 +0000479
Sanjay Patel9b7e6772015-06-23 23:05:08 +0000480/// If all operands to a PHI node are the same "unary" operator and they all are
481/// only used by the PHI, PHI together their inputs, and do the operation once,
482/// to the result of the PHI.
Chris Lattnerde1fede2010-01-05 05:31:55 +0000483Instruction *InstCombiner::FoldPHIArgOpIntoPHI(PHINode &PN) {
David Majnemer27f24472015-11-06 23:59:23 +0000484 // We cannot create a new instruction after the PHI if the terminator is an
485 // EHPad because there is no valid insertion point.
486 if (TerminatorInst *TI = PN.getParent()->getTerminator())
487 if (TI->isEHPad())
488 return nullptr;
489
Chris Lattnerde1fede2010-01-05 05:31:55 +0000490 Instruction *FirstInst = cast<Instruction>(PN.getIncomingValue(0));
491
492 if (isa<GetElementPtrInst>(FirstInst))
493 return FoldPHIArgGEPIntoPHI(PN);
494 if (isa<LoadInst>(FirstInst))
495 return FoldPHIArgLoadIntoPHI(PN);
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000496
Chris Lattnerde1fede2010-01-05 05:31:55 +0000497 // Scan the instruction, looking for input operations that can be folded away.
498 // If all input operands to the phi are the same instruction (e.g. a cast from
499 // the same type or "+42") we can pull the operation through the PHI, reducing
500 // code size and simplifying code.
Craig Topperf40110f2014-04-25 05:29:35 +0000501 Constant *ConstantOp = nullptr;
502 Type *CastSrcTy = nullptr;
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000503
Chris Lattnerde1fede2010-01-05 05:31:55 +0000504 if (isa<CastInst>(FirstInst)) {
505 CastSrcTy = FirstInst->getOperand(0)->getType();
506
507 // Be careful about transforming integer PHIs. We don't want to pessimize
508 // the code by turning an i32 into an i1293.
Duncan Sands19d0b472010-02-16 11:11:14 +0000509 if (PN.getType()->isIntegerTy() && CastSrcTy->isIntegerTy()) {
Chris Lattnerde1fede2010-01-05 05:31:55 +0000510 if (!ShouldChangeType(PN.getType(), CastSrcTy))
Craig Topperf40110f2014-04-25 05:29:35 +0000511 return nullptr;
Chris Lattnerde1fede2010-01-05 05:31:55 +0000512 }
513 } else if (isa<BinaryOperator>(FirstInst) || isa<CmpInst>(FirstInst)) {
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000514 // Can fold binop, compare or shift here if the RHS is a constant,
Chris Lattnerde1fede2010-01-05 05:31:55 +0000515 // otherwise call FoldPHIArgBinOpIntoPHI.
516 ConstantOp = dyn_cast<Constant>(FirstInst->getOperand(1));
Craig Topperf40110f2014-04-25 05:29:35 +0000517 if (!ConstantOp)
Chris Lattnerde1fede2010-01-05 05:31:55 +0000518 return FoldPHIArgBinOpIntoPHI(PN);
519 } else {
Craig Topperf40110f2014-04-25 05:29:35 +0000520 return nullptr; // Cannot fold this operation.
Chris Lattnerde1fede2010-01-05 05:31:55 +0000521 }
522
523 // Check to see if all arguments are the same operation.
524 for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
525 Instruction *I = dyn_cast<Instruction>(PN.getIncomingValue(i));
Craig Topperf40110f2014-04-25 05:29:35 +0000526 if (!I || !I->hasOneUse() || !I->isSameOperationAs(FirstInst))
527 return nullptr;
Chris Lattnerde1fede2010-01-05 05:31:55 +0000528 if (CastSrcTy) {
529 if (I->getOperand(0)->getType() != CastSrcTy)
Craig Topperf40110f2014-04-25 05:29:35 +0000530 return nullptr; // Cast operation must match.
Chris Lattnerde1fede2010-01-05 05:31:55 +0000531 } else if (I->getOperand(1) != ConstantOp) {
Craig Topperf40110f2014-04-25 05:29:35 +0000532 return nullptr;
Chris Lattnerde1fede2010-01-05 05:31:55 +0000533 }
534 }
535
536 // Okay, they are all the same operation. Create a new PHI node of the
537 // correct type, and PHI together all of the LHS's of the instructions.
538 PHINode *NewPN = PHINode::Create(FirstInst->getOperand(0)->getType(),
Jay Foad52131342011-03-30 11:28:46 +0000539 PN.getNumIncomingValues(),
Chris Lattnerde1fede2010-01-05 05:31:55 +0000540 PN.getName()+".in");
Chris Lattnerde1fede2010-01-05 05:31:55 +0000541
542 Value *InVal = FirstInst->getOperand(0);
543 NewPN->addIncoming(InVal, PN.getIncomingBlock(0));
544
545 // Add all operands to the new PHI.
546 for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
547 Value *NewInVal = cast<Instruction>(PN.getIncomingValue(i))->getOperand(0);
548 if (NewInVal != InVal)
Craig Topperf40110f2014-04-25 05:29:35 +0000549 InVal = nullptr;
Chris Lattnerde1fede2010-01-05 05:31:55 +0000550 NewPN->addIncoming(NewInVal, PN.getIncomingBlock(i));
551 }
552
553 Value *PhiVal;
554 if (InVal) {
555 // The new PHI unions all of the same values together. This is really
556 // common, so we handle it intelligently here for compile-time speed.
557 PhiVal = InVal;
558 delete NewPN;
559 } else {
560 InsertNewInstBefore(NewPN, PN);
561 PhiVal = NewPN;
562 }
563
564 // Insert and return the new operation.
Eli Friedman35211c62011-05-27 00:19:40 +0000565 if (CastInst *FirstCI = dyn_cast<CastInst>(FirstInst)) {
566 CastInst *NewCI = CastInst::Create(FirstCI->getOpcode(), PhiVal,
567 PN.getType());
568 NewCI->setDebugLoc(FirstInst->getDebugLoc());
569 return NewCI;
570 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000571
Chris Lattnera8fed472011-02-17 23:01:49 +0000572 if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(FirstInst)) {
573 BinOp = BinaryOperator::Create(BinOp->getOpcode(), PhiVal, ConstantOp);
Silviu Barangae985c762016-04-22 11:21:36 +0000574 BinOp->copyIRFlags(PN.getIncomingValue(0));
575
576 for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i)
577 BinOp->andIRFlags(PN.getIncomingValue(i));
578
Eli Friedman35211c62011-05-27 00:19:40 +0000579 BinOp->setDebugLoc(FirstInst->getDebugLoc());
Chris Lattnera8fed472011-02-17 23:01:49 +0000580 return BinOp;
581 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000582
Chris Lattnerde1fede2010-01-05 05:31:55 +0000583 CmpInst *CIOp = cast<CmpInst>(FirstInst);
Eli Friedman35211c62011-05-27 00:19:40 +0000584 CmpInst *NewCI = CmpInst::Create(CIOp->getOpcode(), CIOp->getPredicate(),
585 PhiVal, ConstantOp);
586 NewCI->setDebugLoc(FirstInst->getDebugLoc());
587 return NewCI;
Chris Lattnerde1fede2010-01-05 05:31:55 +0000588}
589
Sanjay Patel9b7e6772015-06-23 23:05:08 +0000590/// Return true if this PHI node is only used by a PHI node cycle that is dead.
Chris Lattnerde1fede2010-01-05 05:31:55 +0000591static bool DeadPHICycle(PHINode *PN,
Craig Topper71b7b682014-08-21 05:55:13 +0000592 SmallPtrSetImpl<PHINode*> &PotentiallyDeadPHIs) {
Chris Lattnerde1fede2010-01-05 05:31:55 +0000593 if (PN->use_empty()) return true;
594 if (!PN->hasOneUse()) return false;
595
596 // Remember this node, and if we find the cycle, return.
David Blaikie70573dc2014-11-19 07:49:26 +0000597 if (!PotentiallyDeadPHIs.insert(PN).second)
Chris Lattnerde1fede2010-01-05 05:31:55 +0000598 return true;
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000599
Chris Lattnerde1fede2010-01-05 05:31:55 +0000600 // Don't scan crazily complex things.
601 if (PotentiallyDeadPHIs.size() == 16)
602 return false;
603
Chandler Carruthcdf47882014-03-09 03:16:01 +0000604 if (PHINode *PU = dyn_cast<PHINode>(PN->user_back()))
Chris Lattnerde1fede2010-01-05 05:31:55 +0000605 return DeadPHICycle(PU, PotentiallyDeadPHIs);
606
607 return false;
608}
609
Sanjay Patel9b7e6772015-06-23 23:05:08 +0000610/// Return true if this phi node is always equal to NonPhiInVal.
611/// This happens with mutually cyclic phi nodes like:
Chris Lattnerde1fede2010-01-05 05:31:55 +0000612/// z = some value; x = phi (y, z); y = phi (x, z)
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000613static bool PHIsEqualValue(PHINode *PN, Value *NonPhiInVal,
Craig Topper71b7b682014-08-21 05:55:13 +0000614 SmallPtrSetImpl<PHINode*> &ValueEqualPHIs) {
Chris Lattnerde1fede2010-01-05 05:31:55 +0000615 // See if we already saw this PHI node.
David Blaikie70573dc2014-11-19 07:49:26 +0000616 if (!ValueEqualPHIs.insert(PN).second)
Chris Lattnerde1fede2010-01-05 05:31:55 +0000617 return true;
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000618
Chris Lattnerde1fede2010-01-05 05:31:55 +0000619 // Don't scan crazily complex things.
620 if (ValueEqualPHIs.size() == 16)
621 return false;
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000622
Chris Lattnerde1fede2010-01-05 05:31:55 +0000623 // Scan the operands to see if they are either phi nodes or are equal to
624 // the value.
Pete Cooper833f34d2015-05-12 20:05:31 +0000625 for (Value *Op : PN->incoming_values()) {
Chris Lattnerde1fede2010-01-05 05:31:55 +0000626 if (PHINode *OpPN = dyn_cast<PHINode>(Op)) {
627 if (!PHIsEqualValue(OpPN, NonPhiInVal, ValueEqualPHIs))
628 return false;
629 } else if (Op != NonPhiInVal)
630 return false;
631 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000632
Chris Lattnerde1fede2010-01-05 05:31:55 +0000633 return true;
634}
635
Jun Bum Lim10e58e82016-02-11 16:46:13 +0000636/// Return an existing non-zero constant if this phi node has one, otherwise
637/// return constant 1.
Jun Bum Lim339e9722016-02-11 15:50:07 +0000638static ConstantInt *GetAnyNonZeroConstInt(PHINode &PN) {
639 assert(isa<IntegerType>(PN.getType()) && "Expect only intger type phi");
640 for (Value *V : PN.operands())
641 if (auto *ConstVA = dyn_cast<ConstantInt>(V))
642 if (!ConstVA->isZeroValue())
643 return ConstVA;
644 return ConstantInt::get(cast<IntegerType>(PN.getType()), 1);
645}
Chris Lattnerde1fede2010-01-05 05:31:55 +0000646
647namespace {
648struct PHIUsageRecord {
649 unsigned PHIId; // The ID # of the PHI (something determinstic to sort on)
650 unsigned Shift; // The amount shifted.
651 Instruction *Inst; // The trunc instruction.
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000652
Chris Lattnerde1fede2010-01-05 05:31:55 +0000653 PHIUsageRecord(unsigned pn, unsigned Sh, Instruction *User)
654 : PHIId(pn), Shift(Sh), Inst(User) {}
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000655
Chris Lattnerde1fede2010-01-05 05:31:55 +0000656 bool operator<(const PHIUsageRecord &RHS) const {
657 if (PHIId < RHS.PHIId) return true;
658 if (PHIId > RHS.PHIId) return false;
659 if (Shift < RHS.Shift) return true;
660 if (Shift > RHS.Shift) return false;
661 return Inst->getType()->getPrimitiveSizeInBits() <
662 RHS.Inst->getType()->getPrimitiveSizeInBits();
663 }
664};
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000665
Chris Lattnerde1fede2010-01-05 05:31:55 +0000666struct LoweredPHIRecord {
667 PHINode *PN; // The PHI that was lowered.
668 unsigned Shift; // The amount shifted.
669 unsigned Width; // The width extracted.
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000670
Chris Lattner229907c2011-07-18 04:54:35 +0000671 LoweredPHIRecord(PHINode *pn, unsigned Sh, Type *Ty)
Chris Lattnerde1fede2010-01-05 05:31:55 +0000672 : PN(pn), Shift(Sh), Width(Ty->getPrimitiveSizeInBits()) {}
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000673
Chris Lattnerde1fede2010-01-05 05:31:55 +0000674 // Ctor form used by DenseMap.
675 LoweredPHIRecord(PHINode *pn, unsigned Sh)
676 : PN(pn), Shift(Sh), Width(0) {}
677};
Alexander Kornienkof00654e2015-06-23 09:49:53 +0000678}
Chris Lattnerde1fede2010-01-05 05:31:55 +0000679
680namespace llvm {
681 template<>
682 struct DenseMapInfo<LoweredPHIRecord> {
683 static inline LoweredPHIRecord getEmptyKey() {
Craig Topperf40110f2014-04-25 05:29:35 +0000684 return LoweredPHIRecord(nullptr, 0);
Chris Lattnerde1fede2010-01-05 05:31:55 +0000685 }
686 static inline LoweredPHIRecord getTombstoneKey() {
Craig Topperf40110f2014-04-25 05:29:35 +0000687 return LoweredPHIRecord(nullptr, 1);
Chris Lattnerde1fede2010-01-05 05:31:55 +0000688 }
689 static unsigned getHashValue(const LoweredPHIRecord &Val) {
690 return DenseMapInfo<PHINode*>::getHashValue(Val.PN) ^ (Val.Shift>>3) ^
691 (Val.Width>>3);
692 }
693 static bool isEqual(const LoweredPHIRecord &LHS,
694 const LoweredPHIRecord &RHS) {
695 return LHS.PN == RHS.PN && LHS.Shift == RHS.Shift &&
696 LHS.Width == RHS.Width;
697 }
698 };
Alexander Kornienkof00654e2015-06-23 09:49:53 +0000699}
Chris Lattnerde1fede2010-01-05 05:31:55 +0000700
701
Sanjay Patel9b7e6772015-06-23 23:05:08 +0000702/// This is an integer PHI and we know that it has an illegal type: see if it is
703/// only used by trunc or trunc(lshr) operations. If so, we split the PHI into
704/// the various pieces being extracted. This sort of thing is introduced when
705/// SROA promotes an aggregate to large integer values.
Chris Lattnerde1fede2010-01-05 05:31:55 +0000706///
707/// TODO: The user of the trunc may be an bitcast to float/double/vector or an
708/// inttoptr. We should produce new PHIs in the right type.
709///
710Instruction *InstCombiner::SliceUpIllegalIntegerPHI(PHINode &FirstPhi) {
711 // PHIUsers - Keep track of all of the truncated values extracted from a set
712 // of PHIs, along with their offset. These are the things we want to rewrite.
713 SmallVector<PHIUsageRecord, 16> PHIUsers;
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000714
Chris Lattnerde1fede2010-01-05 05:31:55 +0000715 // PHIs are often mutually cyclic, so we keep track of a whole set of PHI
716 // nodes which are extracted from. PHIsToSlice is a set we use to avoid
717 // revisiting PHIs, PHIsInspected is a ordered list of PHIs that we need to
718 // check the uses of (to ensure they are all extracts).
719 SmallVector<PHINode*, 8> PHIsToSlice;
720 SmallPtrSet<PHINode*, 8> PHIsInspected;
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000721
Chris Lattnerde1fede2010-01-05 05:31:55 +0000722 PHIsToSlice.push_back(&FirstPhi);
723 PHIsInspected.insert(&FirstPhi);
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000724
Chris Lattnerde1fede2010-01-05 05:31:55 +0000725 for (unsigned PHIId = 0; PHIId != PHIsToSlice.size(); ++PHIId) {
726 PHINode *PN = PHIsToSlice[PHIId];
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000727
Chris Lattnerde1fede2010-01-05 05:31:55 +0000728 // Scan the input list of the PHI. If any input is an invoke, and if the
729 // input is defined in the predecessor, then we won't be split the critical
730 // edge which is required to insert a truncate. Because of this, we have to
731 // bail out.
732 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
733 InvokeInst *II = dyn_cast<InvokeInst>(PN->getIncomingValue(i));
Craig Topperf40110f2014-04-25 05:29:35 +0000734 if (!II) continue;
Chris Lattnerde1fede2010-01-05 05:31:55 +0000735 if (II->getParent() != PN->getIncomingBlock(i))
736 continue;
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000737
Chris Lattnerde1fede2010-01-05 05:31:55 +0000738 // If we have a phi, and if it's directly in the predecessor, then we have
739 // a critical edge where we need to put the truncate. Since we can't
740 // split the edge in instcombine, we have to bail out.
Craig Topperf40110f2014-04-25 05:29:35 +0000741 return nullptr;
Chris Lattnerde1fede2010-01-05 05:31:55 +0000742 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000743
Chandler Carruthcdf47882014-03-09 03:16:01 +0000744 for (User *U : PN->users()) {
745 Instruction *UserI = cast<Instruction>(U);
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000746
Chris Lattnerde1fede2010-01-05 05:31:55 +0000747 // If the user is a PHI, inspect its uses recursively.
Chandler Carruthcdf47882014-03-09 03:16:01 +0000748 if (PHINode *UserPN = dyn_cast<PHINode>(UserI)) {
David Blaikie70573dc2014-11-19 07:49:26 +0000749 if (PHIsInspected.insert(UserPN).second)
Chris Lattnerde1fede2010-01-05 05:31:55 +0000750 PHIsToSlice.push_back(UserPN);
751 continue;
752 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000753
Chris Lattnerde1fede2010-01-05 05:31:55 +0000754 // Truncates are always ok.
Chandler Carruthcdf47882014-03-09 03:16:01 +0000755 if (isa<TruncInst>(UserI)) {
756 PHIUsers.push_back(PHIUsageRecord(PHIId, 0, UserI));
Chris Lattnerde1fede2010-01-05 05:31:55 +0000757 continue;
758 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000759
Chris Lattnerde1fede2010-01-05 05:31:55 +0000760 // Otherwise it must be a lshr which can only be used by one trunc.
Chandler Carruthcdf47882014-03-09 03:16:01 +0000761 if (UserI->getOpcode() != Instruction::LShr ||
762 !UserI->hasOneUse() || !isa<TruncInst>(UserI->user_back()) ||
763 !isa<ConstantInt>(UserI->getOperand(1)))
Craig Topperf40110f2014-04-25 05:29:35 +0000764 return nullptr;
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000765
Chandler Carruthcdf47882014-03-09 03:16:01 +0000766 unsigned Shift = cast<ConstantInt>(UserI->getOperand(1))->getZExtValue();
767 PHIUsers.push_back(PHIUsageRecord(PHIId, Shift, UserI->user_back()));
Chris Lattnerde1fede2010-01-05 05:31:55 +0000768 }
769 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000770
Chris Lattnerde1fede2010-01-05 05:31:55 +0000771 // If we have no users, they must be all self uses, just nuke the PHI.
772 if (PHIUsers.empty())
Sanjay Patel4b198802016-02-01 22:23:39 +0000773 return replaceInstUsesWith(FirstPhi, UndefValue::get(FirstPhi.getType()));
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000774
Chris Lattnerde1fede2010-01-05 05:31:55 +0000775 // If this phi node is transformable, create new PHIs for all the pieces
776 // extracted out of it. First, sort the users by their offset and size.
777 array_pod_sort(PHIUsers.begin(), PHIUsers.end());
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000778
Matt Arsenaulte6db7602013-09-05 19:48:28 +0000779 DEBUG(dbgs() << "SLICING UP PHI: " << FirstPhi << '\n';
780 for (unsigned i = 1, e = PHIsToSlice.size(); i != e; ++i)
781 dbgs() << "AND USER PHI #" << i << ": " << *PHIsToSlice[i] << '\n';
782 );
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000783
Chris Lattnerde1fede2010-01-05 05:31:55 +0000784 // PredValues - This is a temporary used when rewriting PHI nodes. It is
785 // hoisted out here to avoid construction/destruction thrashing.
786 DenseMap<BasicBlock*, Value*> PredValues;
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000787
Chris Lattnerde1fede2010-01-05 05:31:55 +0000788 // ExtractedVals - Each new PHI we introduce is saved here so we don't
789 // introduce redundant PHIs.
790 DenseMap<LoweredPHIRecord, PHINode*> ExtractedVals;
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000791
Chris Lattnerde1fede2010-01-05 05:31:55 +0000792 for (unsigned UserI = 0, UserE = PHIUsers.size(); UserI != UserE; ++UserI) {
793 unsigned PHIId = PHIUsers[UserI].PHIId;
794 PHINode *PN = PHIsToSlice[PHIId];
795 unsigned Offset = PHIUsers[UserI].Shift;
Chris Lattner229907c2011-07-18 04:54:35 +0000796 Type *Ty = PHIUsers[UserI].Inst->getType();
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000797
Chris Lattnerde1fede2010-01-05 05:31:55 +0000798 PHINode *EltPHI;
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000799
Chris Lattnerde1fede2010-01-05 05:31:55 +0000800 // If we've already lowered a user like this, reuse the previously lowered
801 // value.
Craig Topperf40110f2014-04-25 05:29:35 +0000802 if ((EltPHI = ExtractedVals[LoweredPHIRecord(PN, Offset, Ty)]) == nullptr) {
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000803
Chris Lattnerde1fede2010-01-05 05:31:55 +0000804 // Otherwise, Create the new PHI node for this user.
Jay Foad52131342011-03-30 11:28:46 +0000805 EltPHI = PHINode::Create(Ty, PN->getNumIncomingValues(),
806 PN->getName()+".off"+Twine(Offset), PN);
Chris Lattnerde1fede2010-01-05 05:31:55 +0000807 assert(EltPHI->getType() != PN->getType() &&
808 "Truncate didn't shrink phi?");
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000809
Chris Lattnerde1fede2010-01-05 05:31:55 +0000810 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
811 BasicBlock *Pred = PN->getIncomingBlock(i);
812 Value *&PredVal = PredValues[Pred];
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000813
Chris Lattnerde1fede2010-01-05 05:31:55 +0000814 // If we already have a value for this predecessor, reuse it.
815 if (PredVal) {
816 EltPHI->addIncoming(PredVal, Pred);
817 continue;
818 }
819
820 // Handle the PHI self-reuse case.
821 Value *InVal = PN->getIncomingValue(i);
822 if (InVal == PN) {
823 PredVal = EltPHI;
824 EltPHI->addIncoming(PredVal, Pred);
825 continue;
826 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000827
Chris Lattnerde1fede2010-01-05 05:31:55 +0000828 if (PHINode *InPHI = dyn_cast<PHINode>(PN)) {
829 // If the incoming value was a PHI, and if it was one of the PHIs we
830 // already rewrote it, just use the lowered value.
831 if (Value *Res = ExtractedVals[LoweredPHIRecord(InPHI, Offset, Ty)]) {
832 PredVal = Res;
833 EltPHI->addIncoming(PredVal, Pred);
834 continue;
835 }
836 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000837
Chris Lattnerde1fede2010-01-05 05:31:55 +0000838 // Otherwise, do an extract in the predecessor.
Duncan P. N. Exon Smith9f8aaf22015-10-13 16:59:33 +0000839 Builder->SetInsertPoint(Pred->getTerminator());
Chris Lattnerde1fede2010-01-05 05:31:55 +0000840 Value *Res = InVal;
841 if (Offset)
842 Res = Builder->CreateLShr(Res, ConstantInt::get(InVal->getType(),
843 Offset), "extract");
844 Res = Builder->CreateTrunc(Res, Ty, "extract.t");
845 PredVal = Res;
846 EltPHI->addIncoming(Res, Pred);
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000847
Chris Lattnerde1fede2010-01-05 05:31:55 +0000848 // If the incoming value was a PHI, and if it was one of the PHIs we are
849 // rewriting, we will ultimately delete the code we inserted. This
850 // means we need to revisit that PHI to make sure we extract out the
851 // needed piece.
852 if (PHINode *OldInVal = dyn_cast<PHINode>(PN->getIncomingValue(i)))
853 if (PHIsInspected.count(OldInVal)) {
David Majnemer42531262016-08-12 03:55:06 +0000854 unsigned RefPHIId =
855 find(PHIsToSlice, OldInVal) - PHIsToSlice.begin();
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000856 PHIUsers.push_back(PHIUsageRecord(RefPHIId, Offset,
Chris Lattnerde1fede2010-01-05 05:31:55 +0000857 cast<Instruction>(Res)));
858 ++UserE;
859 }
860 }
861 PredValues.clear();
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000862
Matt Arsenaulte6db7602013-09-05 19:48:28 +0000863 DEBUG(dbgs() << " Made element PHI for offset " << Offset << ": "
Chris Lattnerde1fede2010-01-05 05:31:55 +0000864 << *EltPHI << '\n');
865 ExtractedVals[LoweredPHIRecord(PN, Offset, Ty)] = EltPHI;
866 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000867
Chris Lattnerde1fede2010-01-05 05:31:55 +0000868 // Replace the use of this piece with the PHI node.
Sanjay Patel4b198802016-02-01 22:23:39 +0000869 replaceInstUsesWith(*PHIUsers[UserI].Inst, EltPHI);
Chris Lattnerde1fede2010-01-05 05:31:55 +0000870 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000871
Chris Lattnerde1fede2010-01-05 05:31:55 +0000872 // Replace all the remaining uses of the PHI nodes (self uses and the lshrs)
873 // with undefs.
874 Value *Undef = UndefValue::get(FirstPhi.getType());
875 for (unsigned i = 1, e = PHIsToSlice.size(); i != e; ++i)
Sanjay Patel4b198802016-02-01 22:23:39 +0000876 replaceInstUsesWith(*PHIsToSlice[i], Undef);
877 return replaceInstUsesWith(FirstPhi, Undef);
Chris Lattnerde1fede2010-01-05 05:31:55 +0000878}
879
880// PHINode simplification
881//
882Instruction *InstCombiner::visitPHINode(PHINode &PN) {
Justin Bogner99798402016-08-05 01:06:44 +0000883 if (Value *V = SimplifyInstruction(&PN, DL, &TLI, &DT, &AC))
Sanjay Patel4b198802016-02-01 22:23:39 +0000884 return replaceInstUsesWith(PN, V);
Chris Lattnerde1fede2010-01-05 05:31:55 +0000885
Sanjay Patel95334072015-09-27 20:34:31 +0000886 if (Instruction *Result = FoldPHIArgZextsIntoPHI(PN))
887 return Result;
888
Chris Lattnerde1fede2010-01-05 05:31:55 +0000889 // If all PHI operands are the same operation, pull them through the PHI,
890 // reducing code size.
891 if (isa<Instruction>(PN.getIncomingValue(0)) &&
892 isa<Instruction>(PN.getIncomingValue(1)) &&
893 cast<Instruction>(PN.getIncomingValue(0))->getOpcode() ==
894 cast<Instruction>(PN.getIncomingValue(1))->getOpcode() &&
895 // FIXME: The hasOneUse check will fail for PHIs that use the value more
896 // than themselves more than once.
897 PN.getIncomingValue(0)->hasOneUse())
898 if (Instruction *Result = FoldPHIArgOpIntoPHI(PN))
899 return Result;
900
901 // If this is a trivial cycle in the PHI node graph, remove it. Basically, if
902 // this PHI only has a single use (a PHI), and if that PHI only has one use (a
903 // PHI)... break the cycle.
904 if (PN.hasOneUse()) {
Chandler Carruthcdf47882014-03-09 03:16:01 +0000905 Instruction *PHIUser = cast<Instruction>(PN.user_back());
Chris Lattnerde1fede2010-01-05 05:31:55 +0000906 if (PHINode *PU = dyn_cast<PHINode>(PHIUser)) {
907 SmallPtrSet<PHINode*, 16> PotentiallyDeadPHIs;
908 PotentiallyDeadPHIs.insert(&PN);
909 if (DeadPHICycle(PU, PotentiallyDeadPHIs))
Sanjay Patel4b198802016-02-01 22:23:39 +0000910 return replaceInstUsesWith(PN, UndefValue::get(PN.getType()));
Chris Lattnerde1fede2010-01-05 05:31:55 +0000911 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000912
Chris Lattnerde1fede2010-01-05 05:31:55 +0000913 // If this phi has a single use, and if that use just computes a value for
914 // the next iteration of a loop, delete the phi. This occurs with unused
915 // induction variables, e.g. "for (int j = 0; ; ++j);". Detecting this
916 // common case here is good because the only other things that catch this
917 // are induction variable analysis (sometimes) and ADCE, which is only run
918 // late.
919 if (PHIUser->hasOneUse() &&
920 (isa<BinaryOperator>(PHIUser) || isa<GetElementPtrInst>(PHIUser)) &&
Chandler Carruthcdf47882014-03-09 03:16:01 +0000921 PHIUser->user_back() == &PN) {
Sanjay Patel4b198802016-02-01 22:23:39 +0000922 return replaceInstUsesWith(PN, UndefValue::get(PN.getType()));
Chris Lattnerde1fede2010-01-05 05:31:55 +0000923 }
Jun Bum Lim339e9722016-02-11 15:50:07 +0000924 // When a PHI is used only to be compared with zero, it is safe to replace
925 // an incoming value proved as known nonzero with any non-zero constant.
Jun Bum Lim10e58e82016-02-11 16:46:13 +0000926 // For example, in the code below, the incoming value %v can be replaced
927 // with any non-zero constant based on the fact that the PHI is only used to
928 // be compared with zero and %v is a known non-zero value:
Jun Bum Lim339e9722016-02-11 15:50:07 +0000929 // %v = select %cond, 1, 2
930 // %p = phi [%v, BB] ...
931 // icmp eq, %p, 0
932 auto *CmpInst = dyn_cast<ICmpInst>(PHIUser);
933 // FIXME: To be simple, handle only integer type for now.
934 if (CmpInst && isa<IntegerType>(PN.getType()) && CmpInst->isEquality() &&
935 match(CmpInst->getOperand(1), m_Zero())) {
936 ConstantInt *NonZeroConst = nullptr;
937 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
938 Instruction *CtxI = PN.getIncomingBlock(i)->getTerminator();
939 Value *VA = PN.getIncomingValue(i);
Justin Bogner99798402016-08-05 01:06:44 +0000940 if (isKnownNonZero(VA, DL, 0, &AC, CtxI, &DT)) {
Jun Bum Lim339e9722016-02-11 15:50:07 +0000941 if (!NonZeroConst)
942 NonZeroConst = GetAnyNonZeroConstInt(PN);
943 PN.setIncomingValue(i, NonZeroConst);
944 }
945 }
946 }
Chris Lattnerde1fede2010-01-05 05:31:55 +0000947 }
948
949 // We sometimes end up with phi cycles that non-obviously end up being the
950 // same value, for example:
951 // z = some value; x = phi (y, z); y = phi (x, z)
952 // where the phi nodes don't necessarily need to be in the same block. Do a
953 // quick check to see if the PHI node only contains a single non-phi value, if
954 // so, scan to see if the phi cycle is actually equal to that value.
955 {
Frits van Bommeld6d4f982011-04-16 14:32:34 +0000956 unsigned InValNo = 0, NumIncomingVals = PN.getNumIncomingValues();
Chris Lattnerde1fede2010-01-05 05:31:55 +0000957 // Scan for the first non-phi operand.
Frits van Bommeld6d4f982011-04-16 14:32:34 +0000958 while (InValNo != NumIncomingVals &&
Chris Lattnerde1fede2010-01-05 05:31:55 +0000959 isa<PHINode>(PN.getIncomingValue(InValNo)))
960 ++InValNo;
961
Frits van Bommeld6d4f982011-04-16 14:32:34 +0000962 if (InValNo != NumIncomingVals) {
Jay Foad7d03e9b2011-04-16 14:17:37 +0000963 Value *NonPhiInVal = PN.getIncomingValue(InValNo);
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000964
Chris Lattnerde1fede2010-01-05 05:31:55 +0000965 // Scan the rest of the operands to see if there are any conflicts, if so
966 // there is no need to recursively scan other phis.
Frits van Bommeld6d4f982011-04-16 14:32:34 +0000967 for (++InValNo; InValNo != NumIncomingVals; ++InValNo) {
Chris Lattnerde1fede2010-01-05 05:31:55 +0000968 Value *OpVal = PN.getIncomingValue(InValNo);
969 if (OpVal != NonPhiInVal && !isa<PHINode>(OpVal))
970 break;
971 }
Jim Grosbachbdbd7342013-04-05 21:20:12 +0000972
Chris Lattnerde1fede2010-01-05 05:31:55 +0000973 // If we scanned over all operands, then we have one unique value plus
974 // phi values. Scan PHI nodes to see if they all merge in each other or
975 // the value.
Frits van Bommeld6d4f982011-04-16 14:32:34 +0000976 if (InValNo == NumIncomingVals) {
Chris Lattnerde1fede2010-01-05 05:31:55 +0000977 SmallPtrSet<PHINode*, 16> ValueEqualPHIs;
978 if (PHIsEqualValue(&PN, NonPhiInVal, ValueEqualPHIs))
Sanjay Patel4b198802016-02-01 22:23:39 +0000979 return replaceInstUsesWith(PN, NonPhiInVal);
Chris Lattnerde1fede2010-01-05 05:31:55 +0000980 }
981 }
982 }
983
984 // If there are multiple PHIs, sort their operands so that they all list
985 // the blocks in the same order. This will help identical PHIs be eliminated
986 // by other passes. Other passes shouldn't depend on this for correctness
987 // however.
988 PHINode *FirstPN = cast<PHINode>(PN.getParent()->begin());
989 if (&PN != FirstPN)
990 for (unsigned i = 0, e = FirstPN->getNumIncomingValues(); i != e; ++i) {
991 BasicBlock *BBA = PN.getIncomingBlock(i);
992 BasicBlock *BBB = FirstPN->getIncomingBlock(i);
993 if (BBA != BBB) {
994 Value *VA = PN.getIncomingValue(i);
995 unsigned j = PN.getBasicBlockIndex(BBB);
996 Value *VB = PN.getIncomingValue(j);
997 PN.setIncomingBlock(i, BBB);
998 PN.setIncomingValue(i, VB);
999 PN.setIncomingBlock(j, BBA);
1000 PN.setIncomingValue(j, VA);
1001 // NOTE: Instcombine normally would want us to "return &PN" if we
1002 // modified any of the operands of an instruction. However, since we
1003 // aren't adding or removing uses (just rearranging them) we don't do
1004 // this in this case.
1005 }
1006 }
1007
1008 // If this is an integer PHI and we know that it has an illegal type, see if
1009 // it is only used by trunc or trunc(lshr) operations. If so, we split the
1010 // PHI into the various pieces being extracted. This sort of thing is
1011 // introduced when SROA promotes an aggregate to a single large integer type.
Mehdi Aminia28d91d2015-03-10 02:37:25 +00001012 if (PN.getType()->isIntegerTy() &&
1013 !DL.isLegalInteger(PN.getType()->getPrimitiveSizeInBits()))
Chris Lattnerde1fede2010-01-05 05:31:55 +00001014 if (Instruction *Res = SliceUpIllegalIntegerPHI(PN))
1015 return Res;
Jim Grosbachbdbd7342013-04-05 21:20:12 +00001016
Craig Topperf40110f2014-04-25 05:29:35 +00001017 return nullptr;
Benjamin Kramerf7cc6982010-01-05 13:32:48 +00001018}