LLVM  9.0.0svn
InstCombinePHI.cpp
Go to the documentation of this file.
1 //===- InstCombinePHI.cpp -------------------------------------------------===//
2 //
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
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements the visitPHINode function.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "InstCombineInternal.h"
14 #include "llvm/ADT/STLExtras.h"
15 #include "llvm/ADT/SmallPtrSet.h"
19 #include "llvm/IR/PatternMatch.h"
20 using namespace llvm;
21 using namespace llvm::PatternMatch;
22 
23 #define DEBUG_TYPE "instcombine"
24 
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"));
28 
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));
38 
39  for (unsigned i = 1; i != PN.getNumIncomingValues(); ++i) {
40  auto *I = cast<Instruction>(PN.getIncomingValue(i));
41  Inst->applyMergedLocation(Inst->getDebugLoc(), I->getDebugLoc());
42  }
43 }
44 
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
48 // PHI node:
49 //
50 // Case-1:
51 // bb1:
52 // int_init = PtrToInt(ptr_init)
53 // br label %bb2
54 // bb2:
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)
58 // ...
59 // use(ptr_val2)
60 // ptr_val_inc = ...
61 // inc_val_inc = PtrToInt(ptr_val_inc)
62 //
63 // ==>
64 // bb1:
65 // br label %bb2
66 // bb2:
67 // ptr_val = PHI([ptr_init, %bb1], [ptr_val_inc, %bb2]
68 // ...
69 // use(ptr_val)
70 // ptr_val_inc = ...
71 //
72 // Case-2:
73 // bb1:
74 // int_ptr = BitCast(ptr_ptr)
75 // int_init = Load(int_ptr)
76 // br label %bb2
77 // bb2:
78 // int_val = PHI([int_init, %bb1], [int_val_inc, %bb2]
79 // ptr_val2 = IntToPtr(int_val)
80 // ...
81 // use(ptr_val2)
82 // ptr_val_inc = ...
83 // inc_val_inc = PtrToInt(ptr_val_inc)
84 // ==>
85 // bb1:
86 // ptr_init = Load(ptr_ptr)
87 // br label %bb2
88 // bb2:
89 // ptr_val = PHI([ptr_init, %bb1], [ptr_val_inc, %bb2]
90 // ...
91 // use(ptr_val)
92 // ptr_val_inc = ...
93 // ...
94 //
95 Instruction *InstCombiner::FoldIntegerTypedPHI(PHINode &PN) {
96  if (!PN.getType()->isIntegerTy())
97  return nullptr;
98  if (!PN.hasOneUse())
99  return nullptr;
100 
101  auto *IntToPtr = dyn_cast<IntToPtrInst>(PN.user_back());
102  if (!IntToPtr)
103  return nullptr;
104 
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();
115  }
116 
117  if (Ptr && Ptr == IIP)
118  return true;
119  }
120  return false;
121  };
122 
123  if (!HasPointerUse(IntToPtr))
124  return nullptr;
125 
126  if (DL.getPointerSizeInBits(IntToPtr->getAddressSpace()) !=
127  DL.getTypeSizeInBits(IntToPtr->getOperand(0)->getType()))
128  return nullptr;
129 
130  SmallVector<Value *, 4> AvailablePtrVals;
131  for (unsigned i = 0; i != PN.getNumIncomingValues(); ++i) {
132  Value *Arg = PN.getIncomingValue(i);
133 
134  // First look backward:
135  if (auto *PI = dyn_cast<PtrToIntInst>(Arg)) {
136  AvailablePtrVals.emplace_back(PI->getOperand(0));
137  continue;
138  }
139 
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))) {
146  ArgIntToPtr = U;
147  break;
148  }
149  }
150 
151  if (ArgIntToPtr) {
152  AvailablePtrVals.emplace_back(ArgIntToPtr);
153  continue;
154  }
155 
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);
160  continue;
161  }
162 
163  // For a single use integer load:
164  auto *LoadI = dyn_cast<LoadInst>(Arg);
165  if (!LoadI)
166  return nullptr;
167 
168  if (!LoadI->hasOneUse())
169  return nullptr;
170 
171  // Push the integer typed Load instruction into the available
172  // value set, and fix it up later when the pointer typed PHI
173  // is synthesized.
174  AvailablePtrVals.emplace_back(LoadI);
175  }
176 
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)
187  return nullptr;
188  PHINode *PtrPHI = dyn_cast<PHINode>(II);
189  if (!PtrPHI || PtrPHI == &PN || PtrPHI->getType() != IntToPtr->getType())
190  continue;
191  MatchingPtrPHI = PtrPHI;
192  for (unsigned i = 0; i != PtrPHI->getNumIncomingValues(); ++i) {
193  if (AvailablePtrVals[i] !=
195  MatchingPtrPHI = nullptr;
196  break;
197  }
198  }
199 
200  if (MatchingPtrPHI)
201  break;
202  }
203 
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());
210  }
211 
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);
215  }))
216  return nullptr;
217 
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())
222  return false;
223 
224  auto *Inst = dyn_cast<Instruction>(V);
225  return Inst && Inst->isTerminator();
226  }))
227  return nullptr;
228 
229  PHINode *NewPtrPHI = PHINode::Create(
230  IntToPtr->getType(), PN.getNumIncomingValues(), PN.getName() + ".ptr");
231 
232  InsertNewInstBefore(NewPtrPHI, PN);
234  for (unsigned i = 0; i != PN.getNumIncomingValues(); ++i) {
235  auto *IncomingBB = PN.getIncomingBlock(i);
236  auto *IncomingVal = AvailablePtrVals[i];
237 
238  if (IncomingVal->getType() == IntToPtr->getType()) {
239  NewPtrPHI->addIncoming(IncomingVal, IncomingBB);
240  continue;
241  }
242 
243 #ifndef NDEBUG
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");
249 #endif
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 **
255  // ==>
256  // %v.ptrp = bitcast i64 * %a.ip to float **
257  // %v.cast = load float *, float ** %v.ptrp, align 8
258  Instruction *&CI = Casts[IncomingVal];
259  if (!CI) {
260  CI = CastInst::CreateBitOrPointerCast(IncomingVal, IntToPtr->getType(),
261  IncomingVal->getName() + ".ptr");
262  if (auto *IncomingI = dyn_cast<Instruction>(IncomingVal)) {
263  BasicBlock::iterator InsertPos(IncomingI);
264  InsertPos++;
265  if (isa<PHINode>(IncomingI))
266  InsertPos = IncomingI->getParent()->getFirstInsertionPt();
267  InsertNewInstBefore(CI, *InsertPos);
268  } else {
269  auto *InsertBB = &IncomingBB->getParent()->getEntryBlock();
270  InsertNewInstBefore(CI, *InsertBB->getFirstInsertionPt());
271  }
272  }
273  NewPtrPHI->addIncoming(CI, IncomingBB);
274  }
275 
276  // The PtrToCast + IntToPtr will be simplified later
277  return CastInst::CreateBitOrPointerCast(NewPtrPHI,
278  IntToPtr->getOperand(0)->getType());
279 }
280 
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);
289 
290  Type *LHSType = LHSVal->getType();
291  Type *RHSType = RHSVal->getType();
292 
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) {
296  if (!I || I->getOpcode() != Opc || !I->hasOneUse() ||
297  // Verify type of the LHS matches so we don't fold cmp's of different
298  // types.
299  I->getOperand(0)->getType() != LHSType ||
300  I->getOperand(1)->getType() != RHSType)
301  return nullptr;
302 
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())
306  return nullptr;
307 
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;
311  }
312 
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)
318  return nullptr;
319 
320  // Otherwise, this is safe to transform!
321 
322  Value *InLHS = FirstInst->getOperand(0);
323  Value *InRHS = FirstInst->getOperand(1);
324  PHINode *NewLHS = nullptr, *NewRHS = nullptr;
325  if (!LHSVal) {
326  NewLHS = PHINode::Create(LHSType, PN.getNumIncomingValues(),
327  FirstInst->getOperand(0)->getName() + ".pn");
328  NewLHS->addIncoming(InLHS, PN.getIncomingBlock(0));
329  InsertNewInstBefore(NewLHS, PN);
330  LHSVal = NewLHS;
331  }
332 
333  if (!RHSVal) {
334  NewRHS = PHINode::Create(RHSType, PN.getNumIncomingValues(),
335  FirstInst->getOperand(1)->getName() + ".pn");
336  NewRHS->addIncoming(InRHS, PN.getIncomingBlock(0));
337  InsertNewInstBefore(NewRHS, PN);
338  RHSVal = NewRHS;
339  }
340 
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));
345  if (NewLHS) {
346  Value *NewInLHS = InInst->getOperand(0);
347  NewLHS->addIncoming(NewInLHS, PN.getIncomingBlock(i));
348  }
349  if (NewRHS) {
350  Value *NewInRHS = InInst->getOperand(1);
351  NewRHS->addIncoming(NewInRHS, PN.getIncomingBlock(i));
352  }
353  }
354  }
355 
356  if (CmpInst *CIOp = dyn_cast<CmpInst>(FirstInst)) {
357  CmpInst *NewCI = CmpInst::Create(CIOp->getOpcode(), CIOp->getPredicate(),
358  LHSVal, RHSVal);
359  PHIArgMergedDebugLoc(NewCI, PN);
360  return NewCI;
361  }
362 
363  BinaryOperator *BinOp = cast<BinaryOperator>(FirstInst);
364  BinaryOperator *NewBinOp =
365  BinaryOperator::Create(BinOp->getOpcode(), LHSVal, RHSVal);
366 
367  NewBinOp->copyIRFlags(PN.getIncomingValue(0));
368 
369  for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i)
370  NewBinOp->andIRFlags(PN.getIncomingValue(i));
371 
372  PHIArgMergedDebugLoc(NewBinOp, PN);
373  return NewBinOp;
374 }
375 
376 Instruction *InstCombiner::FoldPHIArgGEPIntoPHI(PHINode &PN) {
377  GetElementPtrInst *FirstInst =cast<GetElementPtrInst>(PN.getIncomingValue(0));
378 
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
382  // constants.
383  bool AllBasePointersAreAllocas = true;
384 
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;
389 
390  bool AllInBounds = true;
391 
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) {
395  if (!GEP || !GEP->hasOneUse() || GEP->getType() != FirstInst->getType() ||
396  GEP->getNumOperands() != FirstInst->getNumOperands())
397  return nullptr;
398 
399  AllInBounds &= GEP->isInBounds();
400 
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;
406 
407  // Compare the operand lists.
408  for (unsigned op = 0, e = FirstInst->getNumOperands(); op != e; ++op) {
409  if (FirstInst->getOperand(op) == GEP->getOperand(op))
410  continue;
411 
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)))
419  return nullptr;
420 
421  if (FirstInst->getOperand(op)->getType() !=GEP->getOperand(op)->getType())
422  return nullptr;
423 
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
427  // block.
428  if (NeededPhi)
429  return nullptr;
430 
431  FixedOperands[op] = nullptr; // Needs a PHI.
432  NeededPhi = true;
433  }
434  }
435 
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)
443  return nullptr;
444 
445  // Otherwise, this is safe to transform. Insert PHI nodes for each operand
446  // that is variable.
447  SmallVector<PHINode*, 16> OperandPhis(FixedOperands.size());
448 
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);
456 
457  NewPN->addIncoming(FirstOp, PN.getIncomingBlock(0));
458  OperandPhis[i] = NewPN;
459  FixedOperands[i] = NewPN;
460  HasAnyPHIs = true;
461  }
462 
463 
464  // Add all operands to the new PHIs.
465  if (HasAnyPHIs) {
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);
469 
470  for (unsigned op = 0, e = OperandPhis.size(); op != e; ++op)
471  if (PHINode *OpPhi = OperandPhis[op])
472  OpPhi->addIncoming(InGEP->getOperand(op), InBB);
473  }
474  }
475 
476  Value *Base = FixedOperands[0];
477  GetElementPtrInst *NewGEP =
479  makeArrayRef(FixedOperands).slice(1));
480  if (AllInBounds) NewGEP->setIsInBounds();
481  PHIArgMergedDebugLoc(NewGEP, PN);
482  return NewGEP;
483 }
484 
485 
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.
489 ///
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
492 /// to a register.
494  BasicBlock::iterator BBI = L->getIterator(), E = L->getParent()->end();
495 
496  for (++BBI; BBI != E; ++BBI)
497  if (BBI->mayWriteToMemory())
498  return false;
499 
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;
509  }
510  isAddressTaken = true;
511  break;
512  }
513 
514  if (!isAddressTaken && AI->isStaticAlloca())
515  return false;
516  }
517 
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())
526  return false;
527 
528  return true;
529 }
530 
531 Instruction *InstCombiner::FoldPHIArgLoadIntoPHI(PHINode &PN) {
532  LoadInst *FirstLI = cast<LoadInst>(PN.getIncomingValue(0));
533 
534  // FIXME: This is overconservative; this transform is allowed in some cases
535  // for atomic operations.
536  if (FirstLI->isAtomic())
537  return nullptr;
538 
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();
547 
548  // We can't sink the load if the loaded value could be modified between the
549  // load and the PHI.
550  if (FirstLI->getParent() != PN.getIncomingBlock(0) ||
552  return nullptr;
553 
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.
557  if (isVolatile &&
558  FirstLI->getParent()->getTerminator()->getNumSuccessors() != 1)
559  return nullptr;
560 
561  // Check to see if all arguments are the same operation.
562  for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
564  if (!LI || !LI->hasOneUse())
565  return nullptr;
566 
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 ||
573  return nullptr;
574 
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))
578  return nullptr;
579 
580  LoadAlignment = std::min(LoadAlignment, LI->getAlignment());
581 
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.
585  if (isVolatile &&
586  LI->getParent()->getTerminator()->getNumSuccessors() != 1)
587  return nullptr;
588  }
589 
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(),
594  PN.getName()+".in");
595 
596  Value *InVal = FirstLI->getOperand(0);
597  NewPN->addIncoming(InVal, PN.getIncomingBlock(0));
598  LoadInst *NewLI =
599  new LoadInst(FirstLI->getType(), NewPN, "", isVolatile, LoadAlignment);
600 
601  unsigned KnownIDs[] = {
612  };
613 
614  for (unsigned ID : KnownIDs)
615  NewLI->setMetadata(ID, FirstLI->getMetadata(ID));
616 
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)
623  InVal = nullptr;
624  NewPN->addIncoming(NewInVal, PN.getIncomingBlock(i));
625  }
626 
627  if (InVal) {
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);
631  delete NewPN;
632  } else {
633  InsertNewInstBefore(NewPN, PN);
634  }
635 
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.
639  if (isVolatile)
640  for (Value *IncValue : PN.incoming_values())
641  cast<LoadInst>(IncValue)->setVolatile(false);
642 
643  PHIArgMergedDebugLoc(NewLI, PN);
644  return NewLI;
645 }
646 
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())
654  if (TI->isEHPad())
655  return nullptr;
656 
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)
662  return nullptr;
663 
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();
669  break;
670  }
671  }
672  if (!NarrowType)
673  return nullptr;
674 
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())
684  return nullptr;
685  NewIncoming.push_back(Zext->getOperand(0));
686  NumZexts++;
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)
691  return nullptr;
692  NewIncoming.push_back(Trunc);
693  NumConsts++;
694  } else {
695  // If it's not a cast or a constant, bail out.
696  return nullptr;
697  }
698  }
699 
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)
707  return nullptr;
708 
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));
716 
717  InsertNewInstBefore(NewPhi, Phi);
718  return CastInst::CreateZExtOrBitCast(NewPhi, Phi.getType());
719 }
720 
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())
728  if (TI->isEHPad())
729  return nullptr;
730 
731  Instruction *FirstInst = cast<Instruction>(PN.getIncomingValue(0));
732 
733  if (isa<GetElementPtrInst>(FirstInst))
734  return FoldPHIArgGEPIntoPHI(PN);
735  if (isa<LoadInst>(FirstInst))
736  return FoldPHIArgLoadIntoPHI(PN);
737 
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;
744 
745  if (isa<CastInst>(FirstInst)) {
746  CastSrcTy = FirstInst->getOperand(0)->getType();
747 
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))
752  return nullptr;
753  }
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));
758  if (!ConstantOp)
759  return FoldPHIArgBinOpIntoPHI(PN);
760  } else {
761  return nullptr; // Cannot fold this operation.
762  }
763 
764  // Check to see if all arguments are the same operation.
765  for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
767  if (!I || !I->hasOneUse() || !I->isSameOperationAs(FirstInst))
768  return nullptr;
769  if (CastSrcTy) {
770  if (I->getOperand(0)->getType() != CastSrcTy)
771  return nullptr; // Cast operation must match.
772  } else if (I->getOperand(1) != ConstantOp) {
773  return nullptr;
774  }
775  }
776 
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(),
781  PN.getName()+".in");
782 
783  Value *InVal = FirstInst->getOperand(0);
784  NewPN->addIncoming(InVal, PN.getIncomingBlock(0));
785 
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)
790  InVal = nullptr;
791  NewPN->addIncoming(NewInVal, PN.getIncomingBlock(i));
792  }
793 
794  Value *PhiVal;
795  if (InVal) {
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.
798  PhiVal = InVal;
799  delete NewPN;
800  } else {
801  InsertNewInstBefore(NewPN, PN);
802  PhiVal = NewPN;
803  }
804 
805  // Insert and return the new operation.
806  if (CastInst *FirstCI = dyn_cast<CastInst>(FirstInst)) {
807  CastInst *NewCI = CastInst::Create(FirstCI->getOpcode(), PhiVal,
808  PN.getType());
809  PHIArgMergedDebugLoc(NewCI, PN);
810  return NewCI;
811  }
812 
813  if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(FirstInst)) {
814  BinOp = BinaryOperator::Create(BinOp->getOpcode(), PhiVal, ConstantOp);
815  BinOp->copyIRFlags(PN.getIncomingValue(0));
816 
817  for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i)
818  BinOp->andIRFlags(PN.getIncomingValue(i));
819 
820  PHIArgMergedDebugLoc(BinOp, PN);
821  return BinOp;
822  }
823 
824  CmpInst *CIOp = cast<CmpInst>(FirstInst);
825  CmpInst *NewCI = CmpInst::Create(CIOp->getOpcode(), CIOp->getPredicate(),
826  PhiVal, ConstantOp);
827  PHIArgMergedDebugLoc(NewCI, PN);
828  return NewCI;
829 }
830 
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;
836 
837  // Remember this node, and if we find the cycle, return.
838  if (!PotentiallyDeadPHIs.insert(PN).second)
839  return true;
840 
841  // Don't scan crazily complex things.
842  if (PotentiallyDeadPHIs.size() == 16)
843  return false;
844 
845  if (PHINode *PU = dyn_cast<PHINode>(PN->user_back()))
846  return DeadPHICycle(PU, PotentiallyDeadPHIs);
847 
848  return false;
849 }
850 
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)
858  return true;
859 
860  // Don't scan crazily complex things.
861  if (ValueEqualPHIs.size() == 16)
862  return false;
863 
864  // Scan the operands to see if they are either phi nodes or are equal to
865  // the value.
866  for (Value *Op : PN->incoming_values()) {
867  if (PHINode *OpPN = dyn_cast<PHINode>(Op)) {
868  if (!PHIsEqualValue(OpPN, NonPhiInVal, ValueEqualPHIs))
869  return false;
870  } else if (Op != NonPhiInVal)
871  return false;
872  }
873 
874  return true;
875 }
876 
877 /// Return an existing non-zero constant if this phi node has one, otherwise
878 /// return constant 1.
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())
884  return ConstVA;
885  return ConstantInt::get(cast<IntegerType>(PN.getType()), 1);
886 }
887 
888 namespace {
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.
893 
894  PHIUsageRecord(unsigned pn, unsigned Sh, Instruction *User)
895  : PHIId(pn), Shift(Sh), Inst(User) {}
896 
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();
904  }
905 };
906 
907 struct LoweredPHIRecord {
908  PHINode *PN; // The PHI that was lowered.
909  unsigned Shift; // The amount shifted.
910  unsigned Width; // The width extracted.
911 
912  LoweredPHIRecord(PHINode *pn, unsigned Sh, Type *Ty)
913  : PN(pn), Shift(Sh), Width(Ty->getPrimitiveSizeInBits()) {}
914 
915  // Ctor form used by DenseMap.
916  LoweredPHIRecord(PHINode *pn, unsigned Sh)
917  : PN(pn), Shift(Sh), Width(0) {}
918 };
919 }
920 
921 namespace llvm {
922  template<>
923  struct DenseMapInfo<LoweredPHIRecord> {
924  static inline LoweredPHIRecord getEmptyKey() {
925  return LoweredPHIRecord(nullptr, 0);
926  }
927  static inline LoweredPHIRecord getTombstoneKey() {
928  return LoweredPHIRecord(nullptr, 1);
929  }
930  static unsigned getHashValue(const LoweredPHIRecord &Val) {
931  return DenseMapInfo<PHINode*>::getHashValue(Val.PN) ^ (Val.Shift>>3) ^
932  (Val.Width>>3);
933  }
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;
938  }
939  };
940 }
941 
942 
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.
947 ///
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.
950 ///
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.
955 
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;
962 
963  PHIsToSlice.push_back(&FirstPhi);
964  PHIsInspected.insert(&FirstPhi);
965 
966  for (unsigned PHIId = 0; PHIId != PHIsToSlice.size(); ++PHIId) {
967  PHINode *PN = PHIsToSlice[PHIId];
968 
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
972  // bail out.
973  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
975  if (!II) continue;
976  if (II->getParent() != PN->getIncomingBlock(i))
977  continue;
978 
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.
982  return nullptr;
983  }
984 
985  for (User *U : PN->users()) {
986  Instruction *UserI = cast<Instruction>(U);
987 
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);
992  continue;
993  }
994 
995  // Truncates are always ok.
996  if (isa<TruncInst>(UserI)) {
997  PHIUsers.push_back(PHIUsageRecord(PHIId, 0, UserI));
998  continue;
999  }
1000 
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)))
1005  return nullptr;
1006 
1007  unsigned Shift = cast<ConstantInt>(UserI->getOperand(1))->getZExtValue();
1008  PHIUsers.push_back(PHIUsageRecord(PHIId, Shift, UserI->user_back()));
1009  }
1010  }
1011 
1012  // If we have no users, they must be all self uses, just nuke the PHI.
1013  if (PHIUsers.empty())
1014  return replaceInstUsesWith(FirstPhi, UndefValue::get(FirstPhi.getType()));
1015 
1016  // If this phi node is transformable, create new PHIs for all the pieces
1017  // extracted out of it. First, sort the users by their offset and size.
1018  array_pod_sort(PHIUsers.begin(), PHIUsers.end());
1019 
1020  LLVM_DEBUG(dbgs() << "SLICING UP PHI: " << FirstPhi << '\n';
1021  for (unsigned i = 1, e = PHIsToSlice.size(); i != e; ++i) dbgs()
1022  << "AND USER PHI #" << i << ": " << *PHIsToSlice[i] << '\n';);
1023 
1024  // PredValues - This is a temporary used when rewriting PHI nodes. It is
1025  // hoisted out here to avoid construction/destruction thrashing.
1026  DenseMap<BasicBlock*, Value*> PredValues;
1027 
1028  // ExtractedVals - Each new PHI we introduce is saved here so we don't
1029  // introduce redundant PHIs.
1031 
1032  for (unsigned UserI = 0, UserE = PHIUsers.size(); UserI != UserE; ++UserI) {
1033  unsigned PHIId = PHIUsers[UserI].PHIId;
1034  PHINode *PN = PHIsToSlice[PHIId];
1035  unsigned Offset = PHIUsers[UserI].Shift;
1036  Type *Ty = PHIUsers[UserI].Inst->getType();
1037 
1038  PHINode *EltPHI;
1039 
1040  // If we've already lowered a user like this, reuse the previously lowered
1041  // value.
1042  if ((EltPHI = ExtractedVals[LoweredPHIRecord(PN, Offset, Ty)]) == nullptr) {
1043 
1044  // Otherwise, Create the new PHI node for this user.
1045  EltPHI = PHINode::Create(Ty, PN->getNumIncomingValues(),
1046  PN->getName()+".off"+Twine(Offset), PN);
1047  assert(EltPHI->getType() != PN->getType() &&
1048  "Truncate didn't shrink phi?");
1049 
1050  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1051  BasicBlock *Pred = PN->getIncomingBlock(i);
1052  Value *&PredVal = PredValues[Pred];
1053 
1054  // If we already have a value for this predecessor, reuse it.
1055  if (PredVal) {
1056  EltPHI->addIncoming(PredVal, Pred);
1057  continue;
1058  }
1059 
1060  // Handle the PHI self-reuse case.
1061  Value *InVal = PN->getIncomingValue(i);
1062  if (InVal == PN) {
1063  PredVal = EltPHI;
1064  EltPHI->addIncoming(PredVal, Pred);
1065  continue;
1066  }
1067 
1068  if (PHINode *InPHI = dyn_cast<PHINode>(PN)) {
1069  // If the incoming value was a PHI, and if it was one of the PHIs we
1070  // already rewrote it, just use the lowered value.
1071  if (Value *Res = ExtractedVals[LoweredPHIRecord(InPHI, Offset, Ty)]) {
1072  PredVal = Res;
1073  EltPHI->addIncoming(PredVal, Pred);
1074  continue;
1075  }
1076  }
1077 
1078  // Otherwise, do an extract in the predecessor.
1079  Builder.SetInsertPoint(Pred->getTerminator());
1080  Value *Res = InVal;
1081  if (Offset)
1082  Res = Builder.CreateLShr(Res, ConstantInt::get(InVal->getType(),
1083  Offset), "extract");
1084  Res = Builder.CreateTrunc(Res, Ty, "extract.t");
1085  PredVal = Res;
1086  EltPHI->addIncoming(Res, Pred);
1087 
1088  // If the incoming value was a PHI, and if it was one of the PHIs we are
1089  // rewriting, we will ultimately delete the code we inserted. This
1090  // means we need to revisit that PHI to make sure we extract out the
1091  // needed piece.
1092  if (PHINode *OldInVal = dyn_cast<PHINode>(PN->getIncomingValue(i)))
1093  if (PHIsInspected.count(OldInVal)) {
1094  unsigned RefPHIId =
1095  find(PHIsToSlice, OldInVal) - PHIsToSlice.begin();
1096  PHIUsers.push_back(PHIUsageRecord(RefPHIId, Offset,
1097  cast<Instruction>(Res)));
1098  ++UserE;
1099  }
1100  }
1101  PredValues.clear();
1102 
1103  LLVM_DEBUG(dbgs() << " Made element PHI for offset " << Offset << ": "
1104  << *EltPHI << '\n');
1105  ExtractedVals[LoweredPHIRecord(PN, Offset, Ty)] = EltPHI;
1106  }
1107 
1108  // Replace the use of this piece with the PHI node.
1109  replaceInstUsesWith(*PHIUsers[UserI].Inst, EltPHI);
1110  }
1111 
1112  // Replace all the remaining uses of the PHI nodes (self uses and the lshrs)
1113  // with undefs.
1114  Value *Undef = UndefValue::get(FirstPhi.getType());
1115  for (unsigned i = 1, e = PHIsToSlice.size(); i != e; ++i)
1116  replaceInstUsesWith(*PHIsToSlice[i], Undef);
1117  return replaceInstUsesWith(FirstPhi, Undef);
1118 }
1119 
1120 // PHINode simplification
1121 //
1123  if (Value *V = SimplifyInstruction(&PN, SQ.getWithInstruction(&PN)))
1124  return replaceInstUsesWith(PN, V);
1125 
1126  if (Instruction *Result = FoldPHIArgZextsIntoPHI(PN))
1127  return Result;
1128 
1129  // If all PHI operands are the same operation, pull them through the PHI,
1130  // reducing code size.
1131  if (isa<Instruction>(PN.getIncomingValue(0)) &&
1132  isa<Instruction>(PN.getIncomingValue(1)) &&
1133  cast<Instruction>(PN.getIncomingValue(0))->getOpcode() ==
1134  cast<Instruction>(PN.getIncomingValue(1))->getOpcode() &&
1135  // FIXME: The hasOneUse check will fail for PHIs that use the value more
1136  // than themselves more than once.
1137  PN.getIncomingValue(0)->hasOneUse())
1138  if (Instruction *Result = FoldPHIArgOpIntoPHI(PN))
1139  return Result;
1140 
1141  // If this is a trivial cycle in the PHI node graph, remove it. Basically, if
1142  // this PHI only has a single use (a PHI), and if that PHI only has one use (a
1143  // PHI)... break the cycle.
1144  if (PN.hasOneUse()) {
1145  if (Instruction *Result = FoldIntegerTypedPHI(PN))
1146  return Result;
1147 
1148  Instruction *PHIUser = cast<Instruction>(PN.user_back());
1149  if (PHINode *PU = dyn_cast<PHINode>(PHIUser)) {
1150  SmallPtrSet<PHINode*, 16> PotentiallyDeadPHIs;
1151  PotentiallyDeadPHIs.insert(&PN);
1152  if (DeadPHICycle(PU, PotentiallyDeadPHIs))
1153  return replaceInstUsesWith(PN, UndefValue::get(PN.getType()));
1154  }
1155 
1156  // If this phi has a single use, and if that use just computes a value for
1157  // the next iteration of a loop, delete the phi. This occurs with unused
1158  // induction variables, e.g. "for (int j = 0; ; ++j);". Detecting this
1159  // common case here is good because the only other things that catch this
1160  // are induction variable analysis (sometimes) and ADCE, which is only run
1161  // late.
1162  if (PHIUser->hasOneUse() &&
1163  (isa<BinaryOperator>(PHIUser) || isa<GetElementPtrInst>(PHIUser)) &&
1164  PHIUser->user_back() == &PN) {
1165  return replaceInstUsesWith(PN, UndefValue::get(PN.getType()));
1166  }
1167  // When a PHI is used only to be compared with zero, it is safe to replace
1168  // an incoming value proved as known nonzero with any non-zero constant.
1169  // For example, in the code below, the incoming value %v can be replaced
1170  // with any non-zero constant based on the fact that the PHI is only used to
1171  // be compared with zero and %v is a known non-zero value:
1172  // %v = select %cond, 1, 2
1173  // %p = phi [%v, BB] ...
1174  // icmp eq, %p, 0
1175  auto *CmpInst = dyn_cast<ICmpInst>(PHIUser);
1176  // FIXME: To be simple, handle only integer type for now.
1177  if (CmpInst && isa<IntegerType>(PN.getType()) && CmpInst->isEquality() &&
1178  match(CmpInst->getOperand(1), m_Zero())) {
1179  ConstantInt *NonZeroConst = nullptr;
1180  for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
1181  Instruction *CtxI = PN.getIncomingBlock(i)->getTerminator();
1182  Value *VA = PN.getIncomingValue(i);
1183  if (isKnownNonZero(VA, DL, 0, &AC, CtxI, &DT)) {
1184  if (!NonZeroConst)
1185  NonZeroConst = GetAnyNonZeroConstInt(PN);
1186  PN.setIncomingValue(i, NonZeroConst);
1187  }
1188  }
1189  }
1190  }
1191 
1192  // We sometimes end up with phi cycles that non-obviously end up being the
1193  // same value, for example:
1194  // z = some value; x = phi (y, z); y = phi (x, z)
1195  // where the phi nodes don't necessarily need to be in the same block. Do a
1196  // quick check to see if the PHI node only contains a single non-phi value, if
1197  // so, scan to see if the phi cycle is actually equal to that value.
1198  {
1199  unsigned InValNo = 0, NumIncomingVals = PN.getNumIncomingValues();
1200  // Scan for the first non-phi operand.
1201  while (InValNo != NumIncomingVals &&
1202  isa<PHINode>(PN.getIncomingValue(InValNo)))
1203  ++InValNo;
1204 
1205  if (InValNo != NumIncomingVals) {
1206  Value *NonPhiInVal = PN.getIncomingValue(InValNo);
1207 
1208  // Scan the rest of the operands to see if there are any conflicts, if so
1209  // there is no need to recursively scan other phis.
1210  for (++InValNo; InValNo != NumIncomingVals; ++InValNo) {
1211  Value *OpVal = PN.getIncomingValue(InValNo);
1212  if (OpVal != NonPhiInVal && !isa<PHINode>(OpVal))
1213  break;
1214  }
1215 
1216  // If we scanned over all operands, then we have one unique value plus
1217  // phi values. Scan PHI nodes to see if they all merge in each other or
1218  // the value.
1219  if (InValNo == NumIncomingVals) {
1220  SmallPtrSet<PHINode*, 16> ValueEqualPHIs;
1221  if (PHIsEqualValue(&PN, NonPhiInVal, ValueEqualPHIs))
1222  return replaceInstUsesWith(PN, NonPhiInVal);
1223  }
1224  }
1225  }
1226 
1227  // If there are multiple PHIs, sort their operands so that they all list
1228  // the blocks in the same order. This will help identical PHIs be eliminated
1229  // by other passes. Other passes shouldn't depend on this for correctness
1230  // however.
1231  PHINode *FirstPN = cast<PHINode>(PN.getParent()->begin());
1232  if (&PN != FirstPN)
1233  for (unsigned i = 0, e = FirstPN->getNumIncomingValues(); i != e; ++i) {
1234  BasicBlock *BBA = PN.getIncomingBlock(i);
1235  BasicBlock *BBB = FirstPN->getIncomingBlock(i);
1236  if (BBA != BBB) {
1237  Value *VA = PN.getIncomingValue(i);
1238  unsigned j = PN.getBasicBlockIndex(BBB);
1239  Value *VB = PN.getIncomingValue(j);
1240  PN.setIncomingBlock(i, BBB);
1241  PN.setIncomingValue(i, VB);
1242  PN.setIncomingBlock(j, BBA);
1243  PN.setIncomingValue(j, VA);
1244  // NOTE: Instcombine normally would want us to "return &PN" if we
1245  // modified any of the operands of an instruction. However, since we
1246  // aren't adding or removing uses (just rearranging them) we don't do
1247  // this in this case.
1248  }
1249  }
1250 
1251  // If this is an integer PHI and we know that it has an illegal type, see if
1252  // it is only used by trunc or trunc(lshr) operations. If so, we split the
1253  // PHI into the various pieces being extracted. This sort of thing is
1254  // introduced when SROA promotes an aggregate to a single large integer type.
1255  if (PN.getType()->isIntegerTy() &&
1256  !DL.isLegalInteger(PN.getType()->getPrimitiveSizeInBits()))
1257  if (Instruction *Res = SliceUpIllegalIntegerPHI(PN))
1258  return Res;
1259 
1260  return nullptr;
1261 }
uint64_t CallInst * C
reference emplace_back(ArgTypes &&... Args)
Definition: SmallVector.h:645
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:636
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
Definition: PatternMatch.h:375
bool isSameOperationAs(const Instruction *I, unsigned flags=0) const
This function determines if the specified instruction executes the same operation as the current one...
This class represents lattice values for constants.
Definition: AllocatorList.h:23
BinaryOps getOpcode() const
Definition: InstrTypes.h:316
bool isAtomic() const
Return true if this instruction has an AtomicOrdering of unordered or higher.
static LoweredPHIRecord getEmptyKey()
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value *> IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:899
bool isTerminator() const
Definition: Instruction.h:128
static CastInst * CreateBitOrPointerCast(Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Create a BitCast, a PtrToInt, or an IntToPTr cast instruction.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1185
An instruction for reading from memory.
Definition: Instructions.h:167
Hexagon Common GEP
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:137
#define op(i)
void copyIRFlags(const Value *V, bool IncludeWrapFlags=true)
Convenience method to copy supported exact, fast-math, and (optionally) wrapping flags from V to this...
op_iterator op_begin()
Definition: User.h:229
static ConstantInt * GetAnyNonZeroConstInt(PHINode &PN)
Return an existing non-zero constant if this phi node has one, otherwise return constant 1...
static bool isSafeAndProfitableToSinkLoad(LoadInst *L)
Return true if we know that it is safe to sink the load out of the block that defines it...
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:343
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:268
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:47
bool isVolatile() const
Return true if this is a load from a volatile memory location.
Definition: Instructions.h:231
int getBasicBlockIndex(const BasicBlock *BB) const
Return the first index of the specified basic block in the value list for this PHI.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:80
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:353
ArrayRef< T > makeArrayRef(const T &OneElt)
Construct an ArrayRef from a single element.
Definition: ArrayRef.h:450
static Optional< unsigned > getOpcode(ArrayRef< VPValue *> Values)
Returns the opcode of Values or ~0 if they do not all agree.
Definition: VPlanSLP.cpp:196
void setIsInBounds(bool b=true)
Set or clear the inbounds flag on this GEP instruction.
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:196
Instruction * SliceUpIllegalIntegerPHI(PHINode &PN)
This is an integer PHI and we know that it has an illegal type: see if it is only used by trunc or tr...
static bool isEqual(const LoweredPHIRecord &LHS, const LoweredPHIRecord &RHS)
Type * getSourceElementType() const
Definition: Instructions.h:970
static Constant * getZExt(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1674
OtherOps getOpcode() const
Get the opcode casted to the right type.
Definition: InstrTypes.h:716
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:244
bool isInBounds() const
Determine whether the GEP has the inbounds flag.
void andIRFlags(const Value *V)
Logical &#39;and&#39; of any supported wrapping, exact, and fast-math flags of V and this instruction...
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:234
static CmpInst * Create(OtherOps Op, Predicate predicate, Value *S1, Value *S2, const Twine &Name="", Instruction *InsertBefore=nullptr)
Construct a compare instruction, given the opcode, the predicate and the two operands.
void combineMetadata(Instruction *K, const Instruction *J, ArrayRef< unsigned > KnownIDs, bool DoesKMove)
Combine the metadata of two instructions so that K can replace J.
Definition: Local.cpp:2288
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:125
An instruction for storing to memory.
Definition: Instructions.h:320
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
Value * getOperand(unsigned i) const
Definition: User.h:169
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:873
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:423
void array_pod_sort(IteratorTy Start, IteratorTy End)
array_pod_sort - This sorts an array with the specified start and end extent.
Definition: STLExtras.h:1082
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:321
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:45
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:41
Value * getIncomingValueForBlock(const BasicBlock *BB) const
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:370
op_iterator op_end()
Definition: User.h:231
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1192
This instruction compares its operands according to the predicate given to the constructor.
amdgpu Simplify well known AMD library false FunctionCallee Value * Arg
op_range operands()
Definition: User.h:237
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
self_iterator getIterator()
Definition: ilist_node.h:81
This class represents a cast from an integer to a pointer.
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1424
size_t size() const
Definition: SmallVector.h:52
static CastInst * CreateZExtOrBitCast(Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Create a ZExt or BitCast cast instruction.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
Instruction * visitPHINode(PHINode &PN)
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1206
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
Definition: Metadata.cpp:1225
size_type size() const
Definition: SmallPtrSet.h:92
Predicate getPredicate(unsigned Condition, unsigned Hint)
Return predicate consisting of specified condition and hint bits.
Definition: PPCPredicates.h:87
Iterator for intrusive lists based on ilist_node.
unsigned getNumOperands() const
Definition: User.h:191
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
This is the shared class of boolean and integer constants.
Definition: Constants.h:83
void setIncomingBlock(unsigned i, BasicBlock *BB)
iterator end()
Definition: BasicBlock.h:270
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:841
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
Definition: Instruction.h:63
static cl::opt< unsigned > MaxNumPhis("instcombine-max-num-phis", cl::init(512), cl::desc("Maximum number phis to handle in intptr/ptrint folding"))
static LoweredPHIRecord getTombstoneKey()
static Constant * getTrunc(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1646
static Constant * get(Type *Ty, uint64_t V, bool isSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:631
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
void applyMergedLocation(const DILocation *LocA, const DILocation *LocB)
Merge 2 debug locations and apply it to the Instruction.
Definition: DebugInfo.cpp:688
unsigned getNumIncomingValues() const
Return the number of incoming edges.
void setOperand(unsigned i, Value *Val)
Definition: User.h:174
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the given value is known to be non-zero when defined.
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), Instruction *InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
iterator_range< user_iterator > users()
Definition: Value.h:399
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:89
static bool DeadPHICycle(PHINode *PN, SmallPtrSetImpl< PHINode *> &PotentiallyDeadPHIs)
Return true if this PHI node is only used by a PHI node cycle that is dead.
static CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name="", Instruction *InsertBefore=nullptr)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass&#39;s ...
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:721
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:324
unsigned getAlignment() const
Return the alignment of the access that is being performed.
Definition: Instructions.h:240
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
#define I(x, y, z)
Definition: MD5.cpp:58
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:322
unsigned getPointerAddressSpace() const
Returns the address space of the pointer operand.
Definition: Instructions.h:290
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:325
unsigned getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
Definition: Type.cpp:114
LLVM Value Representation.
Definition: Value.h:72
bool isEquality() const
This is just a convenience that dispatches to the subclasses.
This file provides internal interfaces used to implement the InstCombine.
static unsigned getHashValue(const LoweredPHIRecord &Val)
Invoke instruction.
bool hasOneUse() const
Return true if there is exactly one user of this value.
Definition: Value.h:412
static bool isVolatile(Instruction *Inst)
void setIncomingValue(unsigned i, Value *V)
#define LLVM_DEBUG(X)
Definition: Debug.h:122
op_range incoming_values()
static bool PHIsEqualValue(PHINode *PN, Value *NonPhiInVal, SmallPtrSetImpl< PHINode *> &ValueEqualPHIs)
Return true if this phi node is always equal to NonPhiInVal.
Value * SimplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
bool use_empty() const
Definition: Value.h:322
bool hasAllConstantIndices() const
Return true if all of the indices of this GEP are constant integers.
const BasicBlock * getParent() const
Definition: Instruction.h:66
an instruction to allocate memory on the stack
Definition: Instructions.h:59