1 //===- InstCombinePHI.cpp -------------------------------------------------===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 // This file implements the visitPHINode function.
11 //===----------------------------------------------------------------------===//
13 #include "InstCombineInternal.h"
14 #include "llvm/ADT/STLExtras.h"
15 #include "llvm/ADT/SmallPtrSet.h"
16 #include "llvm/Analysis/InstructionSimplify.h"
17 #include "llvm/Transforms/Utils/Local.h"
18 #include "llvm/Analysis/ValueTracking.h"
19 #include "llvm/IR/PatternMatch.h"
21 using namespace llvm::PatternMatch
;
23 #define DEBUG_TYPE "instcombine"
25 static cl::opt
<unsigned>
26 MaxNumPhis("instcombine-max-num-phis", cl::init(512),
27 cl::desc("Maximum number phis to handle in intptr/ptrint folding"));
29 /// The PHI arguments will be folded into a single operation with a PHI node
30 /// as input. The debug location of the single operation will be the merged
31 /// locations of the original PHI node arguments.
32 void InstCombiner::PHIArgMergedDebugLoc(Instruction
*Inst
, PHINode
&PN
) {
33 auto *FirstInst
= cast
<Instruction
>(PN
.getIncomingValue(0));
34 Inst
->setDebugLoc(FirstInst
->getDebugLoc());
35 // We do not expect a CallInst here, otherwise, N-way merging of DebugLoc
36 // will be inefficient.
37 assert(!isa
<CallInst
>(Inst
));
39 for (unsigned i
= 1; i
!= PN
.getNumIncomingValues(); ++i
) {
40 auto *I
= cast
<Instruction
>(PN
.getIncomingValue(i
));
41 Inst
->applyMergedLocation(Inst
->getDebugLoc(), I
->getDebugLoc());
45 // Replace Integer typed PHI PN if the PHI's value is used as a pointer value.
46 // If there is an existing pointer typed PHI that produces the same value as PN,
47 // replace PN and the IntToPtr operation with it. Otherwise, synthesize a new
52 // int_init = PtrToInt(ptr_init)
55 // int_val = PHI([int_init, %bb1], [int_val_inc, %bb2]
56 // ptr_val = PHI([ptr_init, %bb1], [ptr_val_inc, %bb2]
57 // ptr_val2 = IntToPtr(int_val)
61 // inc_val_inc = PtrToInt(ptr_val_inc)
67 // ptr_val = PHI([ptr_init, %bb1], [ptr_val_inc, %bb2]
74 // int_ptr = BitCast(ptr_ptr)
75 // int_init = Load(int_ptr)
78 // int_val = PHI([int_init, %bb1], [int_val_inc, %bb2]
79 // ptr_val2 = IntToPtr(int_val)
83 // inc_val_inc = PtrToInt(ptr_val_inc)
86 // ptr_init = Load(ptr_ptr)
89 // ptr_val = PHI([ptr_init, %bb1], [ptr_val_inc, %bb2]
95 Instruction
*InstCombiner::FoldIntegerTypedPHI(PHINode
&PN
) {
96 if (!PN
.getType()->isIntegerTy())
101 auto *IntToPtr
= dyn_cast
<IntToPtrInst
>(PN
.user_back());
105 // Check if the pointer is actually used as pointer:
106 auto HasPointerUse
= [](Instruction
*IIP
) {
107 for (User
*U
: IIP
->users()) {
108 Value
*Ptr
= nullptr;
109 if (LoadInst
*LoadI
= dyn_cast
<LoadInst
>(U
)) {
110 Ptr
= LoadI
->getPointerOperand();
111 } else if (StoreInst
*SI
= dyn_cast
<StoreInst
>(U
)) {
112 Ptr
= SI
->getPointerOperand();
113 } else if (GetElementPtrInst
*GI
= dyn_cast
<GetElementPtrInst
>(U
)) {
114 Ptr
= GI
->getPointerOperand();
117 if (Ptr
&& Ptr
== IIP
)
123 if (!HasPointerUse(IntToPtr
))
126 if (DL
.getPointerSizeInBits(IntToPtr
->getAddressSpace()) !=
127 DL
.getTypeSizeInBits(IntToPtr
->getOperand(0)->getType()))
130 SmallVector
<Value
*, 4> AvailablePtrVals
;
131 for (unsigned i
= 0; i
!= PN
.getNumIncomingValues(); ++i
) {
132 Value
*Arg
= PN
.getIncomingValue(i
);
134 // First look backward:
135 if (auto *PI
= dyn_cast
<PtrToIntInst
>(Arg
)) {
136 AvailablePtrVals
.emplace_back(PI
->getOperand(0));
140 // Next look forward:
141 Value
*ArgIntToPtr
= nullptr;
142 for (User
*U
: Arg
->users()) {
143 if (isa
<IntToPtrInst
>(U
) && U
->getType() == IntToPtr
->getType() &&
144 (DT
.dominates(cast
<Instruction
>(U
), PN
.getIncomingBlock(i
)) ||
145 cast
<Instruction
>(U
)->getParent() == PN
.getIncomingBlock(i
))) {
152 AvailablePtrVals
.emplace_back(ArgIntToPtr
);
156 // If Arg is defined by a PHI, allow it. This will also create
157 // more opportunities iteratively.
158 if (isa
<PHINode
>(Arg
)) {
159 AvailablePtrVals
.emplace_back(Arg
);
163 // For a single use integer load:
164 auto *LoadI
= dyn_cast
<LoadInst
>(Arg
);
168 if (!LoadI
->hasOneUse())
171 // Push the integer typed Load instruction into the available
172 // value set, and fix it up later when the pointer typed PHI
174 AvailablePtrVals
.emplace_back(LoadI
);
177 // Now search for a matching PHI
178 auto *BB
= PN
.getParent();
179 assert(AvailablePtrVals
.size() == PN
.getNumIncomingValues() &&
180 "Not enough available ptr typed incoming values");
181 PHINode
*MatchingPtrPHI
= nullptr;
182 unsigned NumPhis
= 0;
183 for (auto II
= BB
->begin(), EI
= BasicBlock::iterator(BB
->getFirstNonPHI());
184 II
!= EI
; II
++, NumPhis
++) {
185 // FIXME: consider handling this in AggressiveInstCombine
186 if (NumPhis
> MaxNumPhis
)
188 PHINode
*PtrPHI
= dyn_cast
<PHINode
>(II
);
189 if (!PtrPHI
|| PtrPHI
== &PN
|| PtrPHI
->getType() != IntToPtr
->getType())
191 MatchingPtrPHI
= PtrPHI
;
192 for (unsigned i
= 0; i
!= PtrPHI
->getNumIncomingValues(); ++i
) {
193 if (AvailablePtrVals
[i
] !=
194 PtrPHI
->getIncomingValueForBlock(PN
.getIncomingBlock(i
))) {
195 MatchingPtrPHI
= nullptr;
204 if (MatchingPtrPHI
) {
205 assert(MatchingPtrPHI
->getType() == IntToPtr
->getType() &&
206 "Phi's Type does not match with IntToPtr");
207 // The PtrToCast + IntToPtr will be simplified later
208 return CastInst::CreateBitOrPointerCast(MatchingPtrPHI
,
209 IntToPtr
->getOperand(0)->getType());
212 // If it requires a conversion for every PHI operand, do not do it.
213 if (all_of(AvailablePtrVals
, [&](Value
*V
) {
214 return (V
->getType() != IntToPtr
->getType()) || isa
<IntToPtrInst
>(V
);
218 // If any of the operand that requires casting is a terminator
219 // instruction, do not do it.
220 if (any_of(AvailablePtrVals
, [&](Value
*V
) {
221 if (V
->getType() == IntToPtr
->getType())
224 auto *Inst
= dyn_cast
<Instruction
>(V
);
225 return Inst
&& Inst
->isTerminator();
229 PHINode
*NewPtrPHI
= PHINode::Create(
230 IntToPtr
->getType(), PN
.getNumIncomingValues(), PN
.getName() + ".ptr");
232 InsertNewInstBefore(NewPtrPHI
, PN
);
233 SmallDenseMap
<Value
*, Instruction
*> Casts
;
234 for (unsigned i
= 0; i
!= PN
.getNumIncomingValues(); ++i
) {
235 auto *IncomingBB
= PN
.getIncomingBlock(i
);
236 auto *IncomingVal
= AvailablePtrVals
[i
];
238 if (IncomingVal
->getType() == IntToPtr
->getType()) {
239 NewPtrPHI
->addIncoming(IncomingVal
, IncomingBB
);
244 LoadInst
*LoadI
= dyn_cast
<LoadInst
>(IncomingVal
);
245 assert((isa
<PHINode
>(IncomingVal
) ||
246 IncomingVal
->getType()->isPointerTy() ||
247 (LoadI
&& LoadI
->hasOneUse())) &&
248 "Can not replace LoadInst with multiple uses");
250 // Need to insert a BitCast.
251 // For an integer Load instruction with a single use, the load + IntToPtr
252 // cast will be simplified into a pointer load:
253 // %v = load i64, i64* %a.ip, align 8
254 // %v.cast = inttoptr i64 %v to float **
256 // %v.ptrp = bitcast i64 * %a.ip to float **
257 // %v.cast = load float *, float ** %v.ptrp, align 8
258 Instruction
*&CI
= Casts
[IncomingVal
];
260 CI
= CastInst::CreateBitOrPointerCast(IncomingVal
, IntToPtr
->getType(),
261 IncomingVal
->getName() + ".ptr");
262 if (auto *IncomingI
= dyn_cast
<Instruction
>(IncomingVal
)) {
263 BasicBlock::iterator
InsertPos(IncomingI
);
265 if (isa
<PHINode
>(IncomingI
))
266 InsertPos
= IncomingI
->getParent()->getFirstInsertionPt();
267 InsertNewInstBefore(CI
, *InsertPos
);
269 auto *InsertBB
= &IncomingBB
->getParent()->getEntryBlock();
270 InsertNewInstBefore(CI
, *InsertBB
->getFirstInsertionPt());
273 NewPtrPHI
->addIncoming(CI
, IncomingBB
);
276 // The PtrToCast + IntToPtr will be simplified later
277 return CastInst::CreateBitOrPointerCast(NewPtrPHI
,
278 IntToPtr
->getOperand(0)->getType());
281 /// If we have something like phi [add (a,b), add(a,c)] and if a/b/c and the
282 /// adds all have a single use, turn this into a phi and a single binop.
283 Instruction
*InstCombiner::FoldPHIArgBinOpIntoPHI(PHINode
&PN
) {
284 Instruction
*FirstInst
= cast
<Instruction
>(PN
.getIncomingValue(0));
285 assert(isa
<BinaryOperator
>(FirstInst
) || isa
<CmpInst
>(FirstInst
));
286 unsigned Opc
= FirstInst
->getOpcode();
287 Value
*LHSVal
= FirstInst
->getOperand(0);
288 Value
*RHSVal
= FirstInst
->getOperand(1);
290 Type
*LHSType
= LHSVal
->getType();
291 Type
*RHSType
= RHSVal
->getType();
293 // Scan to see if all operands are the same opcode, and all have one use.
294 for (unsigned i
= 1; i
!= PN
.getNumIncomingValues(); ++i
) {
295 Instruction
*I
= dyn_cast
<Instruction
>(PN
.getIncomingValue(i
));
296 if (!I
|| I
->getOpcode() != Opc
|| !I
->hasOneUse() ||
297 // Verify type of the LHS matches so we don't fold cmp's of different
299 I
->getOperand(0)->getType() != LHSType
||
300 I
->getOperand(1)->getType() != RHSType
)
303 // If they are CmpInst instructions, check their predicates
304 if (CmpInst
*CI
= dyn_cast
<CmpInst
>(I
))
305 if (CI
->getPredicate() != cast
<CmpInst
>(FirstInst
)->getPredicate())
308 // Keep track of which operand needs a phi node.
309 if (I
->getOperand(0) != LHSVal
) LHSVal
= nullptr;
310 if (I
->getOperand(1) != RHSVal
) RHSVal
= nullptr;
313 // If both LHS and RHS would need a PHI, don't do this transformation,
314 // because it would increase the number of PHIs entering the block,
315 // which leads to higher register pressure. This is especially
316 // bad when the PHIs are in the header of a loop.
317 if (!LHSVal
&& !RHSVal
)
320 // Otherwise, this is safe to transform!
322 Value
*InLHS
= FirstInst
->getOperand(0);
323 Value
*InRHS
= FirstInst
->getOperand(1);
324 PHINode
*NewLHS
= nullptr, *NewRHS
= nullptr;
326 NewLHS
= PHINode::Create(LHSType
, PN
.getNumIncomingValues(),
327 FirstInst
->getOperand(0)->getName() + ".pn");
328 NewLHS
->addIncoming(InLHS
, PN
.getIncomingBlock(0));
329 InsertNewInstBefore(NewLHS
, PN
);
334 NewRHS
= PHINode::Create(RHSType
, PN
.getNumIncomingValues(),
335 FirstInst
->getOperand(1)->getName() + ".pn");
336 NewRHS
->addIncoming(InRHS
, PN
.getIncomingBlock(0));
337 InsertNewInstBefore(NewRHS
, PN
);
341 // Add all operands to the new PHIs.
342 if (NewLHS
|| NewRHS
) {
343 for (unsigned i
= 1, e
= PN
.getNumIncomingValues(); i
!= e
; ++i
) {
344 Instruction
*InInst
= cast
<Instruction
>(PN
.getIncomingValue(i
));
346 Value
*NewInLHS
= InInst
->getOperand(0);
347 NewLHS
->addIncoming(NewInLHS
, PN
.getIncomingBlock(i
));
350 Value
*NewInRHS
= InInst
->getOperand(1);
351 NewRHS
->addIncoming(NewInRHS
, PN
.getIncomingBlock(i
));
356 if (CmpInst
*CIOp
= dyn_cast
<CmpInst
>(FirstInst
)) {
357 CmpInst
*NewCI
= CmpInst::Create(CIOp
->getOpcode(), CIOp
->getPredicate(),
359 PHIArgMergedDebugLoc(NewCI
, PN
);
363 BinaryOperator
*BinOp
= cast
<BinaryOperator
>(FirstInst
);
364 BinaryOperator
*NewBinOp
=
365 BinaryOperator::Create(BinOp
->getOpcode(), LHSVal
, RHSVal
);
367 NewBinOp
->copyIRFlags(PN
.getIncomingValue(0));
369 for (unsigned i
= 1, e
= PN
.getNumIncomingValues(); i
!= e
; ++i
)
370 NewBinOp
->andIRFlags(PN
.getIncomingValue(i
));
372 PHIArgMergedDebugLoc(NewBinOp
, PN
);
376 Instruction
*InstCombiner::FoldPHIArgGEPIntoPHI(PHINode
&PN
) {
377 GetElementPtrInst
*FirstInst
=cast
<GetElementPtrInst
>(PN
.getIncomingValue(0));
379 SmallVector
<Value
*, 16> FixedOperands(FirstInst
->op_begin(),
380 FirstInst
->op_end());
381 // This is true if all GEP bases are allocas and if all indices into them are
383 bool AllBasePointersAreAllocas
= true;
385 // We don't want to replace this phi if the replacement would require
386 // more than one phi, which leads to higher register pressure. This is
387 // especially bad when the PHIs are in the header of a loop.
388 bool NeededPhi
= false;
390 bool AllInBounds
= true;
392 // Scan to see if all operands are the same opcode, and all have one use.
393 for (unsigned i
= 1; i
!= PN
.getNumIncomingValues(); ++i
) {
394 GetElementPtrInst
*GEP
= dyn_cast
<GetElementPtrInst
>(PN
.getIncomingValue(i
));
395 if (!GEP
|| !GEP
->hasOneUse() || GEP
->getType() != FirstInst
->getType() ||
396 GEP
->getNumOperands() != FirstInst
->getNumOperands())
399 AllInBounds
&= GEP
->isInBounds();
401 // Keep track of whether or not all GEPs are of alloca pointers.
402 if (AllBasePointersAreAllocas
&&
403 (!isa
<AllocaInst
>(GEP
->getOperand(0)) ||
404 !GEP
->hasAllConstantIndices()))
405 AllBasePointersAreAllocas
= false;
407 // Compare the operand lists.
408 for (unsigned op
= 0, e
= FirstInst
->getNumOperands(); op
!= e
; ++op
) {
409 if (FirstInst
->getOperand(op
) == GEP
->getOperand(op
))
412 // Don't merge two GEPs when two operands differ (introducing phi nodes)
413 // if one of the PHIs has a constant for the index. The index may be
414 // substantially cheaper to compute for the constants, so making it a
415 // variable index could pessimize the path. This also handles the case
416 // for struct indices, which must always be constant.
417 if (isa
<ConstantInt
>(FirstInst
->getOperand(op
)) ||
418 isa
<ConstantInt
>(GEP
->getOperand(op
)))
421 if (FirstInst
->getOperand(op
)->getType() !=GEP
->getOperand(op
)->getType())
424 // If we already needed a PHI for an earlier operand, and another operand
425 // also requires a PHI, we'd be introducing more PHIs than we're
426 // eliminating, which increases register pressure on entry to the PHI's
431 FixedOperands
[op
] = nullptr; // Needs a PHI.
436 // If all of the base pointers of the PHI'd GEPs are from allocas, don't
437 // bother doing this transformation. At best, this will just save a bit of
438 // offset calculation, but all the predecessors will have to materialize the
439 // stack address into a register anyway. We'd actually rather *clone* the
440 // load up into the predecessors so that we have a load of a gep of an alloca,
441 // which can usually all be folded into the load.
442 if (AllBasePointersAreAllocas
)
445 // Otherwise, this is safe to transform. Insert PHI nodes for each operand
447 SmallVector
<PHINode
*, 16> OperandPhis(FixedOperands
.size());
449 bool HasAnyPHIs
= false;
450 for (unsigned i
= 0, e
= FixedOperands
.size(); i
!= e
; ++i
) {
451 if (FixedOperands
[i
]) continue; // operand doesn't need a phi.
452 Value
*FirstOp
= FirstInst
->getOperand(i
);
453 PHINode
*NewPN
= PHINode::Create(FirstOp
->getType(), e
,
454 FirstOp
->getName()+".pn");
455 InsertNewInstBefore(NewPN
, PN
);
457 NewPN
->addIncoming(FirstOp
, PN
.getIncomingBlock(0));
458 OperandPhis
[i
] = NewPN
;
459 FixedOperands
[i
] = NewPN
;
464 // Add all operands to the new PHIs.
466 for (unsigned i
= 1, e
= PN
.getNumIncomingValues(); i
!= e
; ++i
) {
467 GetElementPtrInst
*InGEP
=cast
<GetElementPtrInst
>(PN
.getIncomingValue(i
));
468 BasicBlock
*InBB
= PN
.getIncomingBlock(i
);
470 for (unsigned op
= 0, e
= OperandPhis
.size(); op
!= e
; ++op
)
471 if (PHINode
*OpPhi
= OperandPhis
[op
])
472 OpPhi
->addIncoming(InGEP
->getOperand(op
), InBB
);
476 Value
*Base
= FixedOperands
[0];
477 GetElementPtrInst
*NewGEP
=
478 GetElementPtrInst::Create(FirstInst
->getSourceElementType(), Base
,
479 makeArrayRef(FixedOperands
).slice(1));
480 if (AllInBounds
) NewGEP
->setIsInBounds();
481 PHIArgMergedDebugLoc(NewGEP
, PN
);
486 /// Return true if we know that it is safe to sink the load out of the block
487 /// that defines it. This means that it must be obvious the value of the load is
488 /// not changed from the point of the load to the end of the block it is in.
490 /// Finally, it is safe, but not profitable, to sink a load targeting a
491 /// non-address-taken alloca. Doing so will cause us to not promote the alloca
493 static bool isSafeAndProfitableToSinkLoad(LoadInst
*L
) {
494 BasicBlock::iterator BBI
= L
->getIterator(), E
= L
->getParent()->end();
496 for (++BBI
; BBI
!= E
; ++BBI
)
497 if (BBI
->mayWriteToMemory())
500 // Check for non-address taken alloca. If not address-taken already, it isn't
501 // profitable to do this xform.
502 if (AllocaInst
*AI
= dyn_cast
<AllocaInst
>(L
->getOperand(0))) {
503 bool isAddressTaken
= false;
504 for (User
*U
: AI
->users()) {
505 if (isa
<LoadInst
>(U
)) continue;
506 if (StoreInst
*SI
= dyn_cast
<StoreInst
>(U
)) {
507 // If storing TO the alloca, then the address isn't taken.
508 if (SI
->getOperand(1) == AI
) continue;
510 isAddressTaken
= true;
514 if (!isAddressTaken
&& AI
->isStaticAlloca())
518 // If this load is a load from a GEP with a constant offset from an alloca,
519 // then we don't want to sink it. In its present form, it will be
520 // load [constant stack offset]. Sinking it will cause us to have to
521 // materialize the stack addresses in each predecessor in a register only to
522 // do a shared load from register in the successor.
523 if (GetElementPtrInst
*GEP
= dyn_cast
<GetElementPtrInst
>(L
->getOperand(0)))
524 if (AllocaInst
*AI
= dyn_cast
<AllocaInst
>(GEP
->getOperand(0)))
525 if (AI
->isStaticAlloca() && GEP
->hasAllConstantIndices())
531 Instruction
*InstCombiner::FoldPHIArgLoadIntoPHI(PHINode
&PN
) {
532 LoadInst
*FirstLI
= cast
<LoadInst
>(PN
.getIncomingValue(0));
534 // FIXME: This is overconservative; this transform is allowed in some cases
535 // for atomic operations.
536 if (FirstLI
->isAtomic())
539 // When processing loads, we need to propagate two bits of information to the
540 // sunk load: whether it is volatile, and what its alignment is. We currently
541 // don't sink loads when some have their alignment specified and some don't.
542 // visitLoadInst will propagate an alignment onto the load when TD is around,
543 // and if TD isn't around, we can't handle the mixed case.
544 bool isVolatile
= FirstLI
->isVolatile();
545 unsigned LoadAlignment
= FirstLI
->getAlignment();
546 unsigned LoadAddrSpace
= FirstLI
->getPointerAddressSpace();
548 // We can't sink the load if the loaded value could be modified between the
550 if (FirstLI
->getParent() != PN
.getIncomingBlock(0) ||
551 !isSafeAndProfitableToSinkLoad(FirstLI
))
554 // If the PHI is of volatile loads and the load block has multiple
555 // successors, sinking it would remove a load of the volatile value from
556 // the path through the other successor.
558 FirstLI
->getParent()->getTerminator()->getNumSuccessors() != 1)
561 // Check to see if all arguments are the same operation.
562 for (unsigned i
= 1, e
= PN
.getNumIncomingValues(); i
!= e
; ++i
) {
563 LoadInst
*LI
= dyn_cast
<LoadInst
>(PN
.getIncomingValue(i
));
564 if (!LI
|| !LI
->hasOneUse())
567 // We can't sink the load if the loaded value could be modified between
568 // the load and the PHI.
569 if (LI
->isVolatile() != isVolatile
||
570 LI
->getParent() != PN
.getIncomingBlock(i
) ||
571 LI
->getPointerAddressSpace() != LoadAddrSpace
||
572 !isSafeAndProfitableToSinkLoad(LI
))
575 // If some of the loads have an alignment specified but not all of them,
576 // we can't do the transformation.
577 if ((LoadAlignment
!= 0) != (LI
->getAlignment() != 0))
580 LoadAlignment
= std::min(LoadAlignment
, LI
->getAlignment());
582 // If the PHI is of volatile loads and the load block has multiple
583 // successors, sinking it would remove a load of the volatile value from
584 // the path through the other successor.
586 LI
->getParent()->getTerminator()->getNumSuccessors() != 1)
590 // Okay, they are all the same operation. Create a new PHI node of the
591 // correct type, and PHI together all of the LHS's of the instructions.
592 PHINode
*NewPN
= PHINode::Create(FirstLI
->getOperand(0)->getType(),
593 PN
.getNumIncomingValues(),
596 Value
*InVal
= FirstLI
->getOperand(0);
597 NewPN
->addIncoming(InVal
, PN
.getIncomingBlock(0));
599 new LoadInst(FirstLI
->getType(), NewPN
, "", isVolatile
, LoadAlignment
);
601 unsigned KnownIDs
[] = {
602 LLVMContext::MD_tbaa
,
603 LLVMContext::MD_range
,
604 LLVMContext::MD_invariant_load
,
605 LLVMContext::MD_alias_scope
,
606 LLVMContext::MD_noalias
,
607 LLVMContext::MD_nonnull
,
608 LLVMContext::MD_align
,
609 LLVMContext::MD_dereferenceable
,
610 LLVMContext::MD_dereferenceable_or_null
,
611 LLVMContext::MD_access_group
,
614 for (unsigned ID
: KnownIDs
)
615 NewLI
->setMetadata(ID
, FirstLI
->getMetadata(ID
));
617 // Add all operands to the new PHI and combine TBAA metadata.
618 for (unsigned i
= 1, e
= PN
.getNumIncomingValues(); i
!= e
; ++i
) {
619 LoadInst
*LI
= cast
<LoadInst
>(PN
.getIncomingValue(i
));
620 combineMetadata(NewLI
, LI
, KnownIDs
, true);
621 Value
*NewInVal
= LI
->getOperand(0);
622 if (NewInVal
!= InVal
)
624 NewPN
->addIncoming(NewInVal
, PN
.getIncomingBlock(i
));
628 // The new PHI unions all of the same values together. This is really
629 // common, so we handle it intelligently here for compile-time speed.
630 NewLI
->setOperand(0, InVal
);
633 InsertNewInstBefore(NewPN
, PN
);
636 // If this was a volatile load that we are merging, make sure to loop through
637 // and mark all the input loads as non-volatile. If we don't do this, we will
638 // insert a new volatile load and the old ones will not be deletable.
640 for (Value
*IncValue
: PN
.incoming_values())
641 cast
<LoadInst
>(IncValue
)->setVolatile(false);
643 PHIArgMergedDebugLoc(NewLI
, PN
);
647 /// TODO: This function could handle other cast types, but then it might
648 /// require special-casing a cast from the 'i1' type. See the comment in
649 /// FoldPHIArgOpIntoPHI() about pessimizing illegal integer types.
650 Instruction
*InstCombiner::FoldPHIArgZextsIntoPHI(PHINode
&Phi
) {
651 // We cannot create a new instruction after the PHI if the terminator is an
652 // EHPad because there is no valid insertion point.
653 if (Instruction
*TI
= Phi
.getParent()->getTerminator())
657 // Early exit for the common case of a phi with two operands. These are
658 // handled elsewhere. See the comment below where we check the count of zexts
659 // and constants for more details.
660 unsigned NumIncomingValues
= Phi
.getNumIncomingValues();
661 if (NumIncomingValues
< 3)
664 // Find the narrower type specified by the first zext.
665 Type
*NarrowType
= nullptr;
666 for (Value
*V
: Phi
.incoming_values()) {
667 if (auto *Zext
= dyn_cast
<ZExtInst
>(V
)) {
668 NarrowType
= Zext
->getSrcTy();
675 // Walk the phi operands checking that we only have zexts or constants that
676 // we can shrink for free. Store the new operands for the new phi.
677 SmallVector
<Value
*, 4> NewIncoming
;
678 unsigned NumZexts
= 0;
679 unsigned NumConsts
= 0;
680 for (Value
*V
: Phi
.incoming_values()) {
681 if (auto *Zext
= dyn_cast
<ZExtInst
>(V
)) {
682 // All zexts must be identical and have one use.
683 if (Zext
->getSrcTy() != NarrowType
|| !Zext
->hasOneUse())
685 NewIncoming
.push_back(Zext
->getOperand(0));
687 } else if (auto *C
= dyn_cast
<Constant
>(V
)) {
688 // Make sure that constants can fit in the new type.
689 Constant
*Trunc
= ConstantExpr::getTrunc(C
, NarrowType
);
690 if (ConstantExpr::getZExt(Trunc
, C
->getType()) != C
)
692 NewIncoming
.push_back(Trunc
);
695 // If it's not a cast or a constant, bail out.
700 // The more common cases of a phi with no constant operands or just one
701 // variable operand are handled by FoldPHIArgOpIntoPHI() and foldOpIntoPhi()
702 // respectively. foldOpIntoPhi() wants to do the opposite transform that is
703 // performed here. It tries to replicate a cast in the phi operand's basic
704 // block to expose other folding opportunities. Thus, InstCombine will
705 // infinite loop without this check.
706 if (NumConsts
== 0 || NumZexts
< 2)
709 // All incoming values are zexts or constants that are safe to truncate.
710 // Create a new phi node of the narrow type, phi together all of the new
711 // operands, and zext the result back to the original type.
712 PHINode
*NewPhi
= PHINode::Create(NarrowType
, NumIncomingValues
,
713 Phi
.getName() + ".shrunk");
714 for (unsigned i
= 0; i
!= NumIncomingValues
; ++i
)
715 NewPhi
->addIncoming(NewIncoming
[i
], Phi
.getIncomingBlock(i
));
717 InsertNewInstBefore(NewPhi
, Phi
);
718 return CastInst::CreateZExtOrBitCast(NewPhi
, Phi
.getType());
721 /// If all operands to a PHI node are the same "unary" operator and they all are
722 /// only used by the PHI, PHI together their inputs, and do the operation once,
723 /// to the result of the PHI.
724 Instruction
*InstCombiner::FoldPHIArgOpIntoPHI(PHINode
&PN
) {
725 // We cannot create a new instruction after the PHI if the terminator is an
726 // EHPad because there is no valid insertion point.
727 if (Instruction
*TI
= PN
.getParent()->getTerminator())
731 Instruction
*FirstInst
= cast
<Instruction
>(PN
.getIncomingValue(0));
733 if (isa
<GetElementPtrInst
>(FirstInst
))
734 return FoldPHIArgGEPIntoPHI(PN
);
735 if (isa
<LoadInst
>(FirstInst
))
736 return FoldPHIArgLoadIntoPHI(PN
);
738 // Scan the instruction, looking for input operations that can be folded away.
739 // If all input operands to the phi are the same instruction (e.g. a cast from
740 // the same type or "+42") we can pull the operation through the PHI, reducing
741 // code size and simplifying code.
742 Constant
*ConstantOp
= nullptr;
743 Type
*CastSrcTy
= nullptr;
745 if (isa
<CastInst
>(FirstInst
)) {
746 CastSrcTy
= FirstInst
->getOperand(0)->getType();
748 // Be careful about transforming integer PHIs. We don't want to pessimize
749 // the code by turning an i32 into an i1293.
750 if (PN
.getType()->isIntegerTy() && CastSrcTy
->isIntegerTy()) {
751 if (!shouldChangeType(PN
.getType(), CastSrcTy
))
754 } else if (isa
<BinaryOperator
>(FirstInst
) || isa
<CmpInst
>(FirstInst
)) {
755 // Can fold binop, compare or shift here if the RHS is a constant,
756 // otherwise call FoldPHIArgBinOpIntoPHI.
757 ConstantOp
= dyn_cast
<Constant
>(FirstInst
->getOperand(1));
759 return FoldPHIArgBinOpIntoPHI(PN
);
761 return nullptr; // Cannot fold this operation.
764 // Check to see if all arguments are the same operation.
765 for (unsigned i
= 1, e
= PN
.getNumIncomingValues(); i
!= e
; ++i
) {
766 Instruction
*I
= dyn_cast
<Instruction
>(PN
.getIncomingValue(i
));
767 if (!I
|| !I
->hasOneUse() || !I
->isSameOperationAs(FirstInst
))
770 if (I
->getOperand(0)->getType() != CastSrcTy
)
771 return nullptr; // Cast operation must match.
772 } else if (I
->getOperand(1) != ConstantOp
) {
777 // Okay, they are all the same operation. Create a new PHI node of the
778 // correct type, and PHI together all of the LHS's of the instructions.
779 PHINode
*NewPN
= PHINode::Create(FirstInst
->getOperand(0)->getType(),
780 PN
.getNumIncomingValues(),
783 Value
*InVal
= FirstInst
->getOperand(0);
784 NewPN
->addIncoming(InVal
, PN
.getIncomingBlock(0));
786 // Add all operands to the new PHI.
787 for (unsigned i
= 1, e
= PN
.getNumIncomingValues(); i
!= e
; ++i
) {
788 Value
*NewInVal
= cast
<Instruction
>(PN
.getIncomingValue(i
))->getOperand(0);
789 if (NewInVal
!= InVal
)
791 NewPN
->addIncoming(NewInVal
, PN
.getIncomingBlock(i
));
796 // The new PHI unions all of the same values together. This is really
797 // common, so we handle it intelligently here for compile-time speed.
801 InsertNewInstBefore(NewPN
, PN
);
805 // Insert and return the new operation.
806 if (CastInst
*FirstCI
= dyn_cast
<CastInst
>(FirstInst
)) {
807 CastInst
*NewCI
= CastInst::Create(FirstCI
->getOpcode(), PhiVal
,
809 PHIArgMergedDebugLoc(NewCI
, PN
);
813 if (BinaryOperator
*BinOp
= dyn_cast
<BinaryOperator
>(FirstInst
)) {
814 BinOp
= BinaryOperator::Create(BinOp
->getOpcode(), PhiVal
, ConstantOp
);
815 BinOp
->copyIRFlags(PN
.getIncomingValue(0));
817 for (unsigned i
= 1, e
= PN
.getNumIncomingValues(); i
!= e
; ++i
)
818 BinOp
->andIRFlags(PN
.getIncomingValue(i
));
820 PHIArgMergedDebugLoc(BinOp
, PN
);
824 CmpInst
*CIOp
= cast
<CmpInst
>(FirstInst
);
825 CmpInst
*NewCI
= CmpInst::Create(CIOp
->getOpcode(), CIOp
->getPredicate(),
827 PHIArgMergedDebugLoc(NewCI
, PN
);
831 /// Return true if this PHI node is only used by a PHI node cycle that is dead.
832 static bool DeadPHICycle(PHINode
*PN
,
833 SmallPtrSetImpl
<PHINode
*> &PotentiallyDeadPHIs
) {
834 if (PN
->use_empty()) return true;
835 if (!PN
->hasOneUse()) return false;
837 // Remember this node, and if we find the cycle, return.
838 if (!PotentiallyDeadPHIs
.insert(PN
).second
)
841 // Don't scan crazily complex things.
842 if (PotentiallyDeadPHIs
.size() == 16)
845 if (PHINode
*PU
= dyn_cast
<PHINode
>(PN
->user_back()))
846 return DeadPHICycle(PU
, PotentiallyDeadPHIs
);
851 /// Return true if this phi node is always equal to NonPhiInVal.
852 /// This happens with mutually cyclic phi nodes like:
853 /// z = some value; x = phi (y, z); y = phi (x, z)
854 static bool PHIsEqualValue(PHINode
*PN
, Value
*NonPhiInVal
,
855 SmallPtrSetImpl
<PHINode
*> &ValueEqualPHIs
) {
856 // See if we already saw this PHI node.
857 if (!ValueEqualPHIs
.insert(PN
).second
)
860 // Don't scan crazily complex things.
861 if (ValueEqualPHIs
.size() == 16)
864 // Scan the operands to see if they are either phi nodes or are equal to
866 for (Value
*Op
: PN
->incoming_values()) {
867 if (PHINode
*OpPN
= dyn_cast
<PHINode
>(Op
)) {
868 if (!PHIsEqualValue(OpPN
, NonPhiInVal
, ValueEqualPHIs
))
870 } else if (Op
!= NonPhiInVal
)
877 /// Return an existing non-zero constant if this phi node has one, otherwise
878 /// return constant 1.
879 static ConstantInt
*GetAnyNonZeroConstInt(PHINode
&PN
) {
880 assert(isa
<IntegerType
>(PN
.getType()) && "Expect only integer type phi");
881 for (Value
*V
: PN
.operands())
882 if (auto *ConstVA
= dyn_cast
<ConstantInt
>(V
))
883 if (!ConstVA
->isZero())
885 return ConstantInt::get(cast
<IntegerType
>(PN
.getType()), 1);
889 struct PHIUsageRecord
{
890 unsigned PHIId
; // The ID # of the PHI (something determinstic to sort on)
891 unsigned Shift
; // The amount shifted.
892 Instruction
*Inst
; // The trunc instruction.
894 PHIUsageRecord(unsigned pn
, unsigned Sh
, Instruction
*User
)
895 : PHIId(pn
), Shift(Sh
), Inst(User
) {}
897 bool operator<(const PHIUsageRecord
&RHS
) const {
898 if (PHIId
< RHS
.PHIId
) return true;
899 if (PHIId
> RHS
.PHIId
) return false;
900 if (Shift
< RHS
.Shift
) return true;
901 if (Shift
> RHS
.Shift
) return false;
902 return Inst
->getType()->getPrimitiveSizeInBits() <
903 RHS
.Inst
->getType()->getPrimitiveSizeInBits();
907 struct LoweredPHIRecord
{
908 PHINode
*PN
; // The PHI that was lowered.
909 unsigned Shift
; // The amount shifted.
910 unsigned Width
; // The width extracted.
912 LoweredPHIRecord(PHINode
*pn
, unsigned Sh
, Type
*Ty
)
913 : PN(pn
), Shift(Sh
), Width(Ty
->getPrimitiveSizeInBits()) {}
915 // Ctor form used by DenseMap.
916 LoweredPHIRecord(PHINode
*pn
, unsigned Sh
)
917 : PN(pn
), Shift(Sh
), Width(0) {}
923 struct DenseMapInfo
<LoweredPHIRecord
> {
924 static inline LoweredPHIRecord
getEmptyKey() {
925 return LoweredPHIRecord(nullptr, 0);
927 static inline LoweredPHIRecord
getTombstoneKey() {
928 return LoweredPHIRecord(nullptr, 1);
930 static unsigned getHashValue(const LoweredPHIRecord
&Val
) {
931 return DenseMapInfo
<PHINode
*>::getHashValue(Val
.PN
) ^ (Val
.Shift
>>3) ^
934 static bool isEqual(const LoweredPHIRecord
&LHS
,
935 const LoweredPHIRecord
&RHS
) {
936 return LHS
.PN
== RHS
.PN
&& LHS
.Shift
== RHS
.Shift
&&
937 LHS
.Width
== RHS
.Width
;
943 /// This is an integer PHI and we know that it has an illegal type: see if it is
944 /// only used by trunc or trunc(lshr) operations. If so, we split the PHI into
945 /// the various pieces being extracted. This sort of thing is introduced when
946 /// SROA promotes an aggregate to large integer values.
948 /// TODO: The user of the trunc may be an bitcast to float/double/vector or an
949 /// inttoptr. We should produce new PHIs in the right type.
951 Instruction
*InstCombiner::SliceUpIllegalIntegerPHI(PHINode
&FirstPhi
) {
952 // PHIUsers - Keep track of all of the truncated values extracted from a set
953 // of PHIs, along with their offset. These are the things we want to rewrite.
954 SmallVector
<PHIUsageRecord
, 16> PHIUsers
;
956 // PHIs are often mutually cyclic, so we keep track of a whole set of PHI
957 // nodes which are extracted from. PHIsToSlice is a set we use to avoid
958 // revisiting PHIs, PHIsInspected is a ordered list of PHIs that we need to
959 // check the uses of (to ensure they are all extracts).
960 SmallVector
<PHINode
*, 8> PHIsToSlice
;
961 SmallPtrSet
<PHINode
*, 8> PHIsInspected
;
963 PHIsToSlice
.push_back(&FirstPhi
);
964 PHIsInspected
.insert(&FirstPhi
);
966 for (unsigned PHIId
= 0; PHIId
!= PHIsToSlice
.size(); ++PHIId
) {
967 PHINode
*PN
= PHIsToSlice
[PHIId
];
969 // Scan the input list of the PHI. If any input is an invoke, and if the
970 // input is defined in the predecessor, then we won't be split the critical
971 // edge which is required to insert a truncate. Because of this, we have to
973 for (unsigned i
= 0, e
= PN
->getNumIncomingValues(); i
!= e
; ++i
) {
974 InvokeInst
*II
= dyn_cast
<InvokeInst
>(PN
->getIncomingValue(i
));
976 if (II
->getParent() != PN
->getIncomingBlock(i
))
979 // If we have a phi, and if it's directly in the predecessor, then we have
980 // a critical edge where we need to put the truncate. Since we can't
981 // split the edge in instcombine, we have to bail out.
985 for (User
*U
: PN
->users()) {
986 Instruction
*UserI
= cast
<Instruction
>(U
);
988 // If the user is a PHI, inspect its uses recursively.
989 if (PHINode
*UserPN
= dyn_cast
<PHINode
>(UserI
)) {
990 if (PHIsInspected
.insert(UserPN
).second
)
991 PHIsToSlice
.push_back(UserPN
);
995 // Truncates are always ok.
996 if (isa
<TruncInst
>(UserI
)) {
997 PHIUsers
.push_back(PHIUsageRecord(PHIId
, 0, UserI
));
1001 // Otherwise it must be a lshr which can only be used by one trunc.
1002 if (UserI
->getOpcode() != Instruction::LShr
||
1003 !UserI
->hasOneUse() || !isa
<TruncInst
>(UserI
->user_back()) ||
1004 !isa
<ConstantInt
>(UserI
->getOperand(1)))
1007 // Bail on out of range shifts.
1008 unsigned SizeInBits
= UserI
->getType()->getScalarSizeInBits();
1009 if (cast
<ConstantInt
>(UserI
->getOperand(1))->getValue().uge(SizeInBits
))
1012 unsigned Shift
= cast
<ConstantInt
>(UserI
->getOperand(1))->getZExtValue();
1013 PHIUsers
.push_back(PHIUsageRecord(PHIId
, Shift
, UserI
->user_back()));
1017 // If we have no users, they must be all self uses, just nuke the PHI.
1018 if (PHIUsers
.empty())
1019 return replaceInstUsesWith(FirstPhi
, UndefValue::get(FirstPhi
.getType()));
1021 // If this phi node is transformable, create new PHIs for all the pieces
1022 // extracted out of it. First, sort the users by their offset and size.
1023 array_pod_sort(PHIUsers
.begin(), PHIUsers
.end());
1025 LLVM_DEBUG(dbgs() << "SLICING UP PHI: " << FirstPhi
<< '\n';
1026 for (unsigned i
= 1, e
= PHIsToSlice
.size(); i
!= e
; ++i
) dbgs()
1027 << "AND USER PHI #" << i
<< ": " << *PHIsToSlice
[i
] << '\n';);
1029 // PredValues - This is a temporary used when rewriting PHI nodes. It is
1030 // hoisted out here to avoid construction/destruction thrashing.
1031 DenseMap
<BasicBlock
*, Value
*> PredValues
;
1033 // ExtractedVals - Each new PHI we introduce is saved here so we don't
1034 // introduce redundant PHIs.
1035 DenseMap
<LoweredPHIRecord
, PHINode
*> ExtractedVals
;
1037 for (unsigned UserI
= 0, UserE
= PHIUsers
.size(); UserI
!= UserE
; ++UserI
) {
1038 unsigned PHIId
= PHIUsers
[UserI
].PHIId
;
1039 PHINode
*PN
= PHIsToSlice
[PHIId
];
1040 unsigned Offset
= PHIUsers
[UserI
].Shift
;
1041 Type
*Ty
= PHIUsers
[UserI
].Inst
->getType();
1045 // If we've already lowered a user like this, reuse the previously lowered
1047 if ((EltPHI
= ExtractedVals
[LoweredPHIRecord(PN
, Offset
, Ty
)]) == nullptr) {
1049 // Otherwise, Create the new PHI node for this user.
1050 EltPHI
= PHINode::Create(Ty
, PN
->getNumIncomingValues(),
1051 PN
->getName()+".off"+Twine(Offset
), PN
);
1052 assert(EltPHI
->getType() != PN
->getType() &&
1053 "Truncate didn't shrink phi?");
1055 for (unsigned i
= 0, e
= PN
->getNumIncomingValues(); i
!= e
; ++i
) {
1056 BasicBlock
*Pred
= PN
->getIncomingBlock(i
);
1057 Value
*&PredVal
= PredValues
[Pred
];
1059 // If we already have a value for this predecessor, reuse it.
1061 EltPHI
->addIncoming(PredVal
, Pred
);
1065 // Handle the PHI self-reuse case.
1066 Value
*InVal
= PN
->getIncomingValue(i
);
1069 EltPHI
->addIncoming(PredVal
, Pred
);
1073 if (PHINode
*InPHI
= dyn_cast
<PHINode
>(PN
)) {
1074 // If the incoming value was a PHI, and if it was one of the PHIs we
1075 // already rewrote it, just use the lowered value.
1076 if (Value
*Res
= ExtractedVals
[LoweredPHIRecord(InPHI
, Offset
, Ty
)]) {
1078 EltPHI
->addIncoming(PredVal
, Pred
);
1083 // Otherwise, do an extract in the predecessor.
1084 Builder
.SetInsertPoint(Pred
->getTerminator());
1087 Res
= Builder
.CreateLShr(Res
, ConstantInt::get(InVal
->getType(),
1088 Offset
), "extract");
1089 Res
= Builder
.CreateTrunc(Res
, Ty
, "extract.t");
1091 EltPHI
->addIncoming(Res
, Pred
);
1093 // If the incoming value was a PHI, and if it was one of the PHIs we are
1094 // rewriting, we will ultimately delete the code we inserted. This
1095 // means we need to revisit that PHI to make sure we extract out the
1097 if (PHINode
*OldInVal
= dyn_cast
<PHINode
>(PN
->getIncomingValue(i
)))
1098 if (PHIsInspected
.count(OldInVal
)) {
1100 find(PHIsToSlice
, OldInVal
) - PHIsToSlice
.begin();
1101 PHIUsers
.push_back(PHIUsageRecord(RefPHIId
, Offset
,
1102 cast
<Instruction
>(Res
)));
1108 LLVM_DEBUG(dbgs() << " Made element PHI for offset " << Offset
<< ": "
1109 << *EltPHI
<< '\n');
1110 ExtractedVals
[LoweredPHIRecord(PN
, Offset
, Ty
)] = EltPHI
;
1113 // Replace the use of this piece with the PHI node.
1114 replaceInstUsesWith(*PHIUsers
[UserI
].Inst
, EltPHI
);
1117 // Replace all the remaining uses of the PHI nodes (self uses and the lshrs)
1119 Value
*Undef
= UndefValue::get(FirstPhi
.getType());
1120 for (unsigned i
= 1, e
= PHIsToSlice
.size(); i
!= e
; ++i
)
1121 replaceInstUsesWith(*PHIsToSlice
[i
], Undef
);
1122 return replaceInstUsesWith(FirstPhi
, Undef
);
1125 // PHINode simplification
1127 Instruction
*InstCombiner::visitPHINode(PHINode
&PN
) {
1128 if (Value
*V
= SimplifyInstruction(&PN
, SQ
.getWithInstruction(&PN
)))
1129 return replaceInstUsesWith(PN
, V
);
1131 if (Instruction
*Result
= FoldPHIArgZextsIntoPHI(PN
))
1134 // If all PHI operands are the same operation, pull them through the PHI,
1135 // reducing code size.
1136 if (isa
<Instruction
>(PN
.getIncomingValue(0)) &&
1137 isa
<Instruction
>(PN
.getIncomingValue(1)) &&
1138 cast
<Instruction
>(PN
.getIncomingValue(0))->getOpcode() ==
1139 cast
<Instruction
>(PN
.getIncomingValue(1))->getOpcode() &&
1140 // FIXME: The hasOneUse check will fail for PHIs that use the value more
1141 // than themselves more than once.
1142 PN
.getIncomingValue(0)->hasOneUse())
1143 if (Instruction
*Result
= FoldPHIArgOpIntoPHI(PN
))
1146 // If this is a trivial cycle in the PHI node graph, remove it. Basically, if
1147 // this PHI only has a single use (a PHI), and if that PHI only has one use (a
1148 // PHI)... break the cycle.
1149 if (PN
.hasOneUse()) {
1150 if (Instruction
*Result
= FoldIntegerTypedPHI(PN
))
1153 Instruction
*PHIUser
= cast
<Instruction
>(PN
.user_back());
1154 if (PHINode
*PU
= dyn_cast
<PHINode
>(PHIUser
)) {
1155 SmallPtrSet
<PHINode
*, 16> PotentiallyDeadPHIs
;
1156 PotentiallyDeadPHIs
.insert(&PN
);
1157 if (DeadPHICycle(PU
, PotentiallyDeadPHIs
))
1158 return replaceInstUsesWith(PN
, UndefValue::get(PN
.getType()));
1161 // If this phi has a single use, and if that use just computes a value for
1162 // the next iteration of a loop, delete the phi. This occurs with unused
1163 // induction variables, e.g. "for (int j = 0; ; ++j);". Detecting this
1164 // common case here is good because the only other things that catch this
1165 // are induction variable analysis (sometimes) and ADCE, which is only run
1167 if (PHIUser
->hasOneUse() &&
1168 (isa
<BinaryOperator
>(PHIUser
) || isa
<GetElementPtrInst
>(PHIUser
)) &&
1169 PHIUser
->user_back() == &PN
) {
1170 return replaceInstUsesWith(PN
, UndefValue::get(PN
.getType()));
1172 // When a PHI is used only to be compared with zero, it is safe to replace
1173 // an incoming value proved as known nonzero with any non-zero constant.
1174 // For example, in the code below, the incoming value %v can be replaced
1175 // with any non-zero constant based on the fact that the PHI is only used to
1176 // be compared with zero and %v is a known non-zero value:
1177 // %v = select %cond, 1, 2
1178 // %p = phi [%v, BB] ...
1180 auto *CmpInst
= dyn_cast
<ICmpInst
>(PHIUser
);
1181 // FIXME: To be simple, handle only integer type for now.
1182 if (CmpInst
&& isa
<IntegerType
>(PN
.getType()) && CmpInst
->isEquality() &&
1183 match(CmpInst
->getOperand(1), m_Zero())) {
1184 ConstantInt
*NonZeroConst
= nullptr;
1185 for (unsigned i
= 0, e
= PN
.getNumIncomingValues(); i
!= e
; ++i
) {
1186 Instruction
*CtxI
= PN
.getIncomingBlock(i
)->getTerminator();
1187 Value
*VA
= PN
.getIncomingValue(i
);
1188 if (isKnownNonZero(VA
, DL
, 0, &AC
, CtxI
, &DT
)) {
1190 NonZeroConst
= GetAnyNonZeroConstInt(PN
);
1191 PN
.setIncomingValue(i
, NonZeroConst
);
1197 // We sometimes end up with phi cycles that non-obviously end up being the
1198 // same value, for example:
1199 // z = some value; x = phi (y, z); y = phi (x, z)
1200 // where the phi nodes don't necessarily need to be in the same block. Do a
1201 // quick check to see if the PHI node only contains a single non-phi value, if
1202 // so, scan to see if the phi cycle is actually equal to that value.
1204 unsigned InValNo
= 0, NumIncomingVals
= PN
.getNumIncomingValues();
1205 // Scan for the first non-phi operand.
1206 while (InValNo
!= NumIncomingVals
&&
1207 isa
<PHINode
>(PN
.getIncomingValue(InValNo
)))
1210 if (InValNo
!= NumIncomingVals
) {
1211 Value
*NonPhiInVal
= PN
.getIncomingValue(InValNo
);
1213 // Scan the rest of the operands to see if there are any conflicts, if so
1214 // there is no need to recursively scan other phis.
1215 for (++InValNo
; InValNo
!= NumIncomingVals
; ++InValNo
) {
1216 Value
*OpVal
= PN
.getIncomingValue(InValNo
);
1217 if (OpVal
!= NonPhiInVal
&& !isa
<PHINode
>(OpVal
))
1221 // If we scanned over all operands, then we have one unique value plus
1222 // phi values. Scan PHI nodes to see if they all merge in each other or
1224 if (InValNo
== NumIncomingVals
) {
1225 SmallPtrSet
<PHINode
*, 16> ValueEqualPHIs
;
1226 if (PHIsEqualValue(&PN
, NonPhiInVal
, ValueEqualPHIs
))
1227 return replaceInstUsesWith(PN
, NonPhiInVal
);
1232 // If there are multiple PHIs, sort their operands so that they all list
1233 // the blocks in the same order. This will help identical PHIs be eliminated
1234 // by other passes. Other passes shouldn't depend on this for correctness
1236 PHINode
*FirstPN
= cast
<PHINode
>(PN
.getParent()->begin());
1238 for (unsigned i
= 0, e
= FirstPN
->getNumIncomingValues(); i
!= e
; ++i
) {
1239 BasicBlock
*BBA
= PN
.getIncomingBlock(i
);
1240 BasicBlock
*BBB
= FirstPN
->getIncomingBlock(i
);
1242 Value
*VA
= PN
.getIncomingValue(i
);
1243 unsigned j
= PN
.getBasicBlockIndex(BBB
);
1244 Value
*VB
= PN
.getIncomingValue(j
);
1245 PN
.setIncomingBlock(i
, BBB
);
1246 PN
.setIncomingValue(i
, VB
);
1247 PN
.setIncomingBlock(j
, BBA
);
1248 PN
.setIncomingValue(j
, VA
);
1249 // NOTE: Instcombine normally would want us to "return &PN" if we
1250 // modified any of the operands of an instruction. However, since we
1251 // aren't adding or removing uses (just rearranging them) we don't do
1252 // this in this case.
1256 // If this is an integer PHI and we know that it has an illegal type, see if
1257 // it is only used by trunc or trunc(lshr) operations. If so, we split the
1258 // PHI into the various pieces being extracted. This sort of thing is
1259 // introduced when SROA promotes an aggregate to a single large integer type.
1260 if (PN
.getType()->isIntegerTy() &&
1261 !DL
.isLegalInteger(PN
.getType()->getPrimitiveSizeInBits()))
1262 if (Instruction
*Res
= SliceUpIllegalIntegerPHI(PN
))